{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u003cimg align\u003d\"right\" height\u003d\"273\" src\u003d\"http://uva.onlinejudge.org/external/108/p10816.jpg\" width\u003d\"400\" /\u003e\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThere is a group of adventurers who like to travel in the desert. Everyone knows \u003cspan data-scayt_word\u003d\"travelling\" data-scaytid\u003d\"10\"\u003etravelling\u003c/span\u003e in desert can be very dangerous. That\u0026#39;s why they plan their trip carefully every time. There are a lot of factors to consider before they make their final decision.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tOne of the most important factors is the weather. It is undesirable to travel under extremely high temperature. They always try to avoid going to the hottest place. However, it is unavoidable sometimes as it might be on the only way to the destination. To decide where to go, they will pick a route that the highest temperature is minimized. If more than one route satisfy this criterion, they will choose the shortest one.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThere are several oases in the desert where they can take a rest. That means they are \u003cspan data-scayt_word\u003d\"travelling\" data-scaytid\u003d\"11\"\u003etravelling\u003c/span\u003e from oasis to oasis before reaching the destination. They know the lengths and the temperatures of the paths between oases. You are to \u003cb\u003ewrite a program\u003c/b\u003e and plan the route for them.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tInput consists of several test cases. Your program must process all of them.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThe first line contains two integers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eE\u003c/i\u003e (1 \u0026le; \u003ci\u003eN\u003c/i\u003e \u0026le; 100; 1 \u0026le; \u003ci\u003eE\u003c/i\u003e \u0026le; 10000) where \u003ci\u003eN\u003c/i\u003e represents the number of oasis and \u003ci\u003eE\u003c/i\u003e represents the number of paths between them. Next line contains two distinct integers \u003ci\u003eS\u003c/i\u003e and \u003ci\u003eT\u003c/i\u003e (1 \u0026le; \u003ci\u003eS\u003c/i\u003e, \u003ci\u003eT\u003c/i\u003e \u0026le; \u003ci\u003eN\u003c/i\u003e) representing the starting point and the destination respectively. The following \u003ci\u003eE\u003c/i\u003e lines are the information the group gathered. Each line contains 2 integers \u003ci\u003eX, Y\u003c/i\u003e and 2 real numbers \u003ci\u003eR\u003c/i\u003e and \u003ci\u003eD\u003c/i\u003e (1 \u0026le; \u003ci\u003eX\u003c/i\u003e, \u003ci\u003eY\u003c/i\u003e \u0026le; \u003ci\u003eN\u003c/i\u003e; 20 \u0026le; \u003ci\u003eR\u003c/i\u003e \u0026le; 50; 0 \u0026lt; \u003ci\u003eD\u003c/i\u003e \u0026le; 40). It means there is a path between \u003ci\u003eX\u003c/i\u003e and \u003ci\u003eY\u003c/i\u003e, with length \u003ci\u003eD\u003c/i\u003e km and highest temperature \u003ci\u003eR\u003c/i\u003e \u003ci\u003e\u003csup\u003eo\u003c/sup\u003eC\u003c/i\u003e. Each real number has exactly one digit after the decimal point. There might be more than one path between a pair of oases.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tPrint two lines for each test case. The first line should give the route you find, and the second should contain its length and maximum temperature.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e6 9\r\n1 6\r\n1 2 37.1 10.2\r\n2 3 40.5 20.7\r\n3 4 42.8 19.0\r\n3 1 38.3 15.8\r\n4 5 39.7 11.1\r\n6 3 36.0 22.5\r\n5 6 43.9 10.2\r\n2 6 44.2 15.2\r\n4 6 34.2 17.4\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e1 3 6\r\n38.3 38.3\u003c/pre\u003e"}}]}