1)
4 4
1 2 9 15
1 4 0 8
2 3 20 30
3 1 31 0
1 4 9 30

->
4
1 3 4 2

2)
2 3
1 2 0 5
1 1 110 80
1 1 90 0
1 2 100 6

->
3
2 3 1

3)
3 6
1 2 50 55
2 1 55 40
1 2 0 1
1 3 41 80
3 2 80 12
2 1 15 0
1 2 49 7

->
6
1 2 4 5 6 3

n= ; k= ; m=n*k <=100000
------------------------
n m
1 2 1 1
1 2 2 2
.......
1 2 k k
2 3 1 1
2 3 2 2
.......
2 3 k k
.......
.......
.......
n 1 1 0
n 1 2 1
n 1 3 2
.......
n 1 k k-1
1 1 k 0
---------------------------
for n=3, k=2 Ans. 2 4 6 1 3 5