시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB5310921.429%

문제

$N$ 개의 정점과 $M$ 개의 간선이 있는 그래프가 있다. 각 간선에는 방향성이 있으며, 음이 아닌 정수 가중치를 가진다.

모든 $2 \le i \le N$ 에 대해서, 1번 정점에서 $i$ 번 정점으로 가는 두 개의 겹치지 않는 경로들 중, 비용 합의 최솟값을 계산하라. 경로가 겹치지 않는다는 것은, 같은 간선을 공유하지 않는다는 것이다. 경로의 비용은, 경로에 속하는 간선의 가중치를 전부 합한 값이다.

입력

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

  • 첫 번째 줄에 정수 $N, M$이 주어진다.
  • 이후 $M$ 개의 줄에 세 정수 $u_i, v_i, w_i$ 가 주어진다. $u_i$ 번 정점에서 $v_i$ 번 정점으로 가는 가중치 $w_i$ 의 간선이 존재한다는 뜻이다.

출력

각 테스트 케이스 마다 한 줄에 $N-1$ 개의 정수를 출력하라. 이 중 $i$ 번째 정수는, 1번 정점에서 $i+1$ 번 정점으로 가는 두 개의 겹치지 않는 경로들 중, 비용 합의 최솟값을 뜻한다. 만약 두 개의 겹치지 않는 경로가 존재하지 않는다면 -1을 출력하라.

제한

  • $1 \le u_i , v_i \le N$
  • $u_i \neq v_i$
  • $i \neq j \iff (u_i, v_i) \neq (u_j, v_j)$
  • $0 \le w_i \le 10^9$
  • 1번 정점에서 모든 정점으로 도달할 수 있다. 
  • 한 입력 파일에 대해, $N$ 의 합은 $100\,000$ 이하이다.
  • 한 입력 파일에 대해, $M$ 의 합은 $1\,000\,000$ 이하이다.

예제 입력 1

3
3 4
1 2 1
1 3 2
2 3 3
3 2 4
2 2
1 2 1
2 1 0
5 7
1 2 4
2 3 3
1 3 8
3 5 3
4 5 2
5 4 7
1 5 1

예제 출력 1

7 6
-1
-1 15 -1 11

예제 입력 2

2
4 9
1 2 18
2 3 1
3 4 11
4 3 2
4 1 30
3 1 24
3 2 22
1 3 18
2 4 1
4 5
1 2 2
1 3 14
1 4 4
2 1 20
2 3 30

예제 출력 2

58 37 48
-1 46 -1
W3sicHJvYmxlbV9pZCI6IjIyMjc4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViNDUwIFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPiROJCBcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVhY2ZjICRNJCBcdWFjMWNcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVhYzA0XHVjMTIwXHVjNWQwXHViMjk0IFx1YmMyOVx1ZDVhNVx1YzEzMVx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyBcdWFjMDBcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCAkMiBcXGxlIGkgXFxsZSBOJCBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCAxXHViYzg4IFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyAkaSQgXHViYzg4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YjRlNCBcdWM5MTEsIFx1YmU0NFx1YzZhOSBcdWQ1NjlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1Yjc3Yy4gXHVhY2JkXHViODVjXHVhYzAwIFx1YWNiOVx1Y2U1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwLCBcdWFjMTlcdWM3NDAgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFjYmRcdWI4NWNcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzQwLCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWI5N2MgXHVjODA0XHViZDgwIFx1ZDU2OVx1ZDU1YyBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOCBUQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBUQ1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzBjOCBcdWM5MDRcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICROLCBNJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc3NFx1ZDZjNCAkTSQgXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4ICR1X2ksIHZfaSwgd19pJCBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkdV9pJCBcdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjICR2X2kkIFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWMwMFx1YzkxMVx1Y2U1OCAkd19pJCBcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQgXHVkNTVjIFx1YzkwNFx1YzVkMCAkTi0xJCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy4gXHVjNzc0IFx1YzkxMSAkaSQgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCwgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDBcdWMxMWMgJGkrMSQgXHViYzg4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YjRlNCBcdWM5MTEsIFx1YmU0NFx1YzZhOSBcdWQ1NjlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCA8Y29kZT4tMTxcL2NvZGU+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZSB1X2kgLCZuYnNwO3ZfaSBcXGxlIE4kPFwvbGk+XHJcblx0PGxpPiR1X2kgXFxuZXEgdl9pJDxcL2xpPlxyXG5cdDxsaT4kaSBcXG5lcSBqIFxcaWZmICh1X2ksIHZfaSkgXFxuZXEgKHVfaiwgdl9qKSQ8XC9saT5cclxuXHQ8bGk+JDAgXFxsZSB3X2kgXFxsZSAxMF45JDxcL2xpPlxyXG5cdDxsaT4xXHViYzg4IFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1YjNjNFx1YjJlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5cdWQ1NWMgXHVjNzg1XHViODI1IFx1ZDMwY1x1Yzc3Y1x1YzVkMCBcdWIzMDBcdWQ1NzQsICROJCBcdWM3NTggXHVkNTY5XHVjNzQwICQxMDBcXCwwMDAkIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVkNTVjIFx1Yzc4NVx1YjgyNSBcdWQzMGNcdWM3N2NcdWM1ZDAgXHViMzAwXHVkNTc0LCAkTSQgXHVjNzU4IFx1ZDU2OVx1Yzc0MCAkMVxcLDAwMFxcLDAwMCQgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjIyNzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJbnRlcmVzdCIsImRlc2NyaXB0aW9uIjoiPHA+Qml0Z2FyZCBpcyBhIHRocml2aW5nIG1ldHJvcG9saXMuIEF0IHRoaXMgcG9pbnQsIGl0IGhhcyBleGFjdGx5ICRuJCBjcm9zc3JvYWRzIChudW1iZXJlZCBmcm9tIDEsIHRvICRuJCksIGNvbm5lY3RlZCBieSAkbSQgb25lIHdheSByb2Fkcy4gRWFjaCByb2FkIGhhcyBzb21lIG5vbi1uZWdhdGl2ZSBsZW5ndGguIFRoZSBvbmx5IHBvaW50IG9mIHJvYWQgaW50ZXJzZWN0aW9ucyBhcmUgY3Jvc3Nyb2FkcywgdGhvdWdoIHRoZXJlIG1heSBiZSBtYW55IHR1bm5lbHMgYW5kIHZpYWR1Y3RzLiBJdCBpcyBrbm93biB0aGF0IGVhY2ggY3Jvc3Nyb2FkIGlzIHJlYWNoYWJsZSBmcm9tIHRoZSBjcm9zc3JvYWQgbnVtYmVyIDEsIGJ1dCBpdCBkb2VzbiYjMzk7dCBoYXZlIHRvIGJlIHRydWUsIHRoYXQgZWFjaCBjcm9zc3JvYWQgaXMgcmVhY2hhYmxlIGZyb20gYW55IG90aGVyIGNyb3Nzcm9hZC48XC9wPlxyXG5cclxuPHA+Qml0Z2FyZCBleHBhbmRzIGFuZCBnZXQgd2VhbHRoeSBzbyBxdWlja2x5LCB0aGF0IHNvbWUgcGVvcGxlIGJlY2FtZSBpbnRlcmVzdGVkIGluIHJvYmJpbmcgaXQmIzM5O3MgZmFjaWxpdGllcy4gVHdvIG9mIHN1Y2ggaW5kaXZpZHVhbHMgYXJlIEJvbGVrIGFuZCBMb2xlay4gVG8gYWNoaWV2ZSB0aGVpciBnb2FsIHRoZXkgbW92ZWQgdG8gdGhlIGNyb3Nzcm9hZCBudW1iZXIgJDEkLCBhbmQgbm93IHRoZXkgd2FudCB0byByb2IgdGhlIHNob3AgbmVhcmJ5IHNvbWUgb3RoZXIgY3Jvc3Nyb2FkLiBJZiB0aGV5IGRlY2lkZSB0byBhc3NhdWx0IHNob3AgbmVhcmJ5IHRoZSAkaSQtdGggY3Jvc3Nyb2FkLCB0byBtaW5pbWl6ZSB0aGUgcmlzayBvZiBiZWluZyBhc3NvY2lhdGVkIHdpdGggZWFjaCBvdGhlciwgdGhleSB3aWxsIGdvIHRvIHRoaXMgY3Jvc3Nyb2FkIGJ5IHR3byBlZGdlLXNlcGFyYXRlZCBwYXRocy4gSWYgc3VjaCBwYXRocyBleGlzdCwgQm9sZWsgYW5kIExvbGVrIHdhbnQgdG8ga25vdyB0aGUgbWluaW11bSBzdW0gb2YgbGVuZ3RocyBvZiBzdWNoIHBhdGhzLjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCBjcm9zc3JvYWQgb3RoZXIgdGhhbiB0aGUgZmlyc3Qgb25lLCBoZWxwIEJvbGVrIGFuZCBMb2xlayB0byBkZXRlcm1pbmUgdGhpcyB2YWx1ZSBvciBzdGF0ZSB0aGF0IHRoaXMgaXMgaW1wb3NzaWJsZSB0byBmaW5kIHR3byBzdWNoIHBhdGhzLiAmbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lIG9uZSBpbnRlZ2VyICRaIFxcbGUgMTAwJCBpcyBnaXZlbiwgZGVub3RpbmcgbnVtYmVyIG9mIHRlc3RjYXNlcyBkZXNjcmliZWQgaW4gZm9sbG93aW5nIGxpbmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgdGVzdCBjYXNlIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkbiQgYW5kICRtJCwgZGVub3RpbmcgdGhlIG51bWJlciBjcm9zc3JvYWRzIGFuZCB0aGUgbnVtYmVyIG9mIG9uZS13YXkgcm9hZHMgaW4gQml0Z2FyZC48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgJG0kIGZvbGxvd2luZyBsaW5lcyBjb250YWlucyBhIGRlc2NyaXB0aW9uIG9mIHJvYWRzLiAkaSQtdGggbGluZSBjb25zaXN0cyBvZiB0aHJlZSBpbnRlZ2VyIG51bWJlcnMgJGFfaSwgYl9pJCBhbmQgJGNfaSQgKCRhX2kgXFxuZXEgYl9pIFxcaW4gWzEsIG5dLCBjIFxcaW4gWzAsIDEwXjldJCksIGRlbm90aW5nIHRoYXQgdGhlcmUgaXMgcm9hZCBzdGFydGluZyBhdCBjcm9zc3JvYWQgJGFfaSQgY29ubmVjdGluZyBpdCB0byBjcm9zc3JvYWQgbnVtYmVyICRiX2kkLCB3aGljaCBoYXMgbGVuZ3RoICRjX2kkLiBZb3UgY2FuIGFzc3VtZSB0aGF0IGZvciBlYWNoIG9yZGVyZWQgcGFpciBvZiBjcm9zc3JvYWRzIHRoZXJlIGlzIGF0IG1vc3Qgb25lIHJvYWQgY29ubmVjdGluZyB0aGVtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQgZm9yIGVhY2ggdGVzdCBjYXNlIHNob3VsZCBjb25zaXN0IG9mICRuLTEkIChwb3NzaWJseSB6ZXJvKSBudW1iZXJzIGRlbm90aW5nIHJlc3VsdHMgZm9yIGFsbCB0aGUgY3Jvc3Nyb2FkcyBleGNlcHQgZnJvbSB0aGUgZmlyc3Qgb25lLiBJZiBpdCBpcyBwb3NzaWJsZSB0byBmaW5kIHR3byBlZGdlLWRpc2pvaW50IHBhdGhzIGZyb20gdmVydGV4ICQxJCB0byB2ZXJ0ZXggJGkkLCB0aGVuICRpJC10aCBudW1iZXIgc2hvdWxkIGJlIGVxdWFsIHRvIG1pbmltdW0gbGVuZ3RoIG9mIHN1bSBvZiBzdWNoIHBhdGhzLiBJbiBvdGhlciBjYXNlIHlvdSBzaG91bGQgb3V0cHV0IDxjb2RlPi0xPFwvY29kZT4gZm9yIHRoaXMgY3Jvc3Nyb2FkLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+U3VtcyBvdmVyIHRoZSB2YWx1ZXMgb2YgcGFyYW1ldGVycyAkbiQgYW5kICRtJCBvdmVyIGFsbCB0ZXN0IGNhc2VzIGRvIG5vdCBleGNlZWQgJDEwXjUkIGFuZCAkMTBeNiQgcmVzcGVjdGl2ZWx5LiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuIn1d