{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eJason lives in a country consists of N cities, numbered from 1 to N. Any two cities are connected by two directed roads. Walking on each road takes exactly one day. There are M places of interests in the country, numbered from 1 to M. Each place i locates on the road from city s[i] to city t[i]. Jason is planning a trip. For each place i, he wants to visit at least k[i] times. He also wants to finish his trip as soon as possible because he has a lot of homework to do. He can start from any city. Could you help him arrange a travel route?\u003cbr\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T (1 \u0026lt;\u003d T \u0026lt;\u003d 15), indicating the number of test cases.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tFor each test case:\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThe first line contains two integers N and M (1 \u0026lt;\u003d N \u0026lt;\u003d 100,000, 1 \u0026lt;\u003d M \u0026lt;\u003d 300,000), indicating there are N cities and M places of interests in the country.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThen M lines follow, the i-th line contains three integers s[i], t[i], and k[i] (1 \u0026lt;\u003d s[i],t[i] \u0026lt;\u003d N, s[i] ≠ t[i], 1 \u0026lt;\u003d k[i] \u0026lt;\u003d 300,000, ∑k[i] \u0026lt;\u003d 300,000), indicating place i locates on the road from city s[i] to city t[i], and should be visited at least k[i] times.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tIt is guaranteed that no two places locate on the same road."}},{"title":"Output","value":{"format":"HTML","content":"For each test case:\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThe first line contains one integer t, indicating the minimum time Jason has to spend.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThe second line contains t+1 integers, separated by spaces, indicating the city numbers that Jason is going to travel in order. If there are several possible answers, output any one of them."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n4 3\r\n1 2 3\r\n3 4 2\r\n4 3 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n1 2 3 4 3 4 3 1 2 1 2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}