Alibaba is a famous company for their excellent B2B business; recently alibaba has heard their client’s complains about the slower deliver in B2B business, so they want to reform their transportation system. As we all know, the traffic in china is totally a mass, so Alibaba want to find out the key road and the useless road in their transportation system. Now for simplification, we assume Alibaba’s transportation system is a single source and single sink network, source is alibaba’s headquarters HangZhou(numbered as 1), and sink is BeiJing(numbered as n). Each road in the network has a capacity for transport stuff; Alibaba knows the maximum unit stuff this network can deliver from HangZhou to BeiJing, now they just want to know the key roads which must be full delivered in any maximum transport route (means the delivered stuff must be their capacity in any maximum transport route), and the useless roads which can be empty in some maximum transport route (means this road is not necessary, it can delivered nothing in some maximum transport route)

       First a number T indicates there are T cases followed.(T <= 10)

Two integer n m denote the number of city and number of roads in the network (source is 1, sink is n) (n <= 200, m <= 2000)

       Then m lines followed which formatted as A B C means there is a road from A to B with C unit capacity. (One way road) (1<=A<=n, 1<=B<=n, 1<=C<=5000)

       For each test case output two lines, first line show the ID of roads which is key roads (sorted as their order in input) and second line show the ID of roads which is useless roads(sorted as their order in input), ID is the order of this roads in input.

1
6 8
1 2 3
2 4 3
4 6 3
2 5 3
1 3 3
3 4 3
3 5 3
5 6 3

1 3 5 8
2 4 6 7

      Roads 1->2, 1->3, 4->6, 5->6 should be full in any maximum transport route. So they are key roads and two groups of roads 2->4, 3->5 and 2->5, 3->4 can be swapped in the maximum transport route so they are useless roads.