시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 156 31 23 20.721%

문제

라인 제로 놀이 동산에 새로운 미로가 생겼다. 미로는 방 n개와 방을 연결하는 통로 m개로 이루어져 있다. 통로는 ci 색으로 색칠되어져 있다. 미로는 입구는 1번 방이고, 출구는 n번 방이다. 미로에 들어가려면 헬리콥터를 타고 1번 방으로 낙하해야 한다.

미로를 만든 선영이는 다음날 미로 탈출 대회를 개최하려고 한다. 참가자는 1번 방 에서 출발하고, n번 방에 도착할 때까지 지난 복도의 색상을 모두 종이에 적는다. 대회를 우승하려면 종이에 적은 숫자의 개수가 적어야 한다. 또, 종이에 적은 숫자의 개수가 같은 경우에는 가장 이상적인 경로인 사람이 우승하게 된다. 다른 경로보다 모두 사전 순으로 앞서는 경로를 이상적인 경로라고 한다.

미로의 정보가 주어졌을 때, 1번 방에서 n번 방으로 가는 가장 이상적인 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 방의 수 n과 복도의 수 m이 주어진다. (2 ≤ n ≤ 100,000, 1 ≤ m ≤ 200,000) 다음 m개 줄에는 복도의 정보가 주어지며, 정보는 세 정수 ai, bi, ci로 이루어져 있다. ai와 bi는 복도가 연결하는 방의 번호이고, ci는 복도의 색상이다. (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109) 복도는 양방향이며, 두 방을 연결하는 복도의 개수는 1개보다 많을 수도 있다. 또, 자기 자신으로 되돌아오는 복도가 존재할 수도 있다. 항상 1번 방에서 n번 방으로 갈 수 있는 미로만 입력으로 주어진다.

출력

첫째 줄에 1번 방에서 n번 방으로 가는 최단 경로의 길이를 출력한다. 둘째 줄에는 가장 이상적인 경로의 색을 지나가는 순서대로 출력한다.

예제 입력 1

4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

예제 출력 1

2
1 3

힌트

수열 (a1, a2, ..., ak)가 수열 (b1, b2, ..., bk)보다 사전 순으로 앞서러면, ai < bi와 모든 j<i에 대해서 aj = bj를 만족하는 i가 존재해야 한다.

W3sicHJvYmxlbV9pZCI6IjM1MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWMwYzFcdWM4MDFcdWM3NzggXHVhY2JkXHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI3N2NcdWM3NzggXHVjODFjXHViODVjIFx1YjE4MFx1Yzc3NCBcdWIzZDlcdWMwYjBcdWM1ZDAgXHVjMGM4XHViODVjXHVjNmI0IFx1YmJmOFx1Yjg1Y1x1YWMwMCBcdWMwZGRcdWFjYmNcdWIyZTQuIFx1YmJmOFx1Yjg1Y1x1YjI5NCBcdWJjMjkgblx1YWMxY1x1YzY0MCBcdWJjMjlcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1ZDFiNVx1Yjg1YyBtXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDFiNVx1Yjg1Y1x1YjI5NCBjPHN1Yj5pPFwvc3ViPiBcdWMwYzlcdWM3M2NcdWI4NWMgXHVjMGM5XHVjZTYwXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViYmY4XHViODVjXHViMjk0IFx1Yzc4NVx1YWQ2Y1x1YjI5NCAxXHViYzg4IFx1YmMyOVx1Yzc3NFx1YWNlMCwgXHVjZDljXHVhZDZjXHViMjk0IG5cdWJjODggXHViYzI5XHVjNzc0XHViMmU0LiBcdWJiZjhcdWI4NWNcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHViODI0XHViYTc0IFx1ZDVlY1x1YjlhY1x1Y2Y2NVx1ZDEzMFx1Yjk3YyBcdWQwYzBcdWFjZTAgMVx1YmM4OCBcdWJjMjlcdWM3M2NcdWI4NWMgXHViMDk5XHVkNTU4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYmY4XHViODVjXHViOTdjIFx1YjljY1x1YjRlMCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjXHViMGEwIFx1YmJmOFx1Yjg1YyBcdWQwYzhcdWNkOWMgXHViMzAwXHVkNjhjXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjI5NCAxXHViYzg4IFx1YmMyOSBcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHVhY2UwLCBuXHViYzg4IFx1YmMyOVx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1YzljMFx1YjA5YyBcdWJjZjVcdWIzYzRcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjODAxXHViMjk0XHViMmU0LiBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVjNmIwXHVjMmI5XHVkNTU4XHViODI0XHViYTc0IFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM4MDFcdWM3NDAgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4MDFcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM4MDFcdWM3NDAgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3NzRcdWMwYzFcdWM4MDFcdWM3NzggXHVhY2JkXHViODVjXHVjNzc4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM2YjBcdWMyYjlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWIyZTRcdWI5NzggXHVhY2JkXHViODVjXHViY2Y0XHViMmU0IFx1YmFhOFx1YjQ1MCBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzExY1x1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjNzc0XHVjMGMxXHVjODAxXHVjNzc4IFx1YWNiZFx1Yjg1Y1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmJmOFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgMVx1YmM4OCBcdWJjMjlcdWM1ZDBcdWMxMWMgblx1YmM4OCBcdWJjMjlcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3NzRcdWMwYzFcdWM4MDFcdWM3NzggXHVhY2JkXHViODVjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMjlcdWM3NTggXHVjMjE4IG5cdWFjZmMgXHViY2Y1XHViM2M0XHVjNzU4IFx1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBuICZsZTsgMTAwLDAwMCwgMSAmbGU7IG0gJmxlOyAyMDAsMDAwKSBcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViY2Y1XHViM2M0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YzgxNVx1YmNmNFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiwgYzxzdWI+aTxcL3N1Yj5cdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gYTxzdWI+aTxcL3N1Yj5cdWM2NDAgYjxzdWI+aTxcL3N1Yj5cdWIyOTQgXHViY2Y1XHViM2M0XHVhYzAwIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHVhY2UwLCBjPHN1Yj5pPFwvc3ViPlx1YjI5NCBcdWJjZjVcdWIzYzRcdWM3NTggXHVjMGM5XHVjMGMxXHVjNzc0XHViMmU0LiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPiAmbGU7IG4sIDEgJmxlOyBjPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPikgXHViY2Y1XHViM2M0XHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNVx1Yzc3NFx1YmE3MCwgXHViNDUwIFx1YmMyOVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViY2Y1XHViM2M0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAxXHVhYzFjXHViY2Y0XHViMmU0IFx1YjljZVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM3M2NcdWI4NWMgXHViNDE4XHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0IFx1YmNmNVx1YjNjNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVkNTZkXHVjMGMxIDFcdWJjODggXHViYzI5XHVjNWQwXHVjMTFjIG5cdWJjODggXHViYzI5XHVjNzNjXHViODVjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmJmOFx1Yjg1Y1x1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgMVx1YmM4OCBcdWJjMjlcdWM1ZDBcdWMxMWMgblx1YmM4OCBcdWJjMjlcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzc0XHVjMGMxXHVjODAxXHVjNzc4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWMwYzlcdWM3NDQgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzIxOFx1YzVmNCAoYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPms8XC9zdWI+KVx1YWMwMCBcdWMyMThcdWM1ZjQgKGI8c3ViPjE8XC9zdWI+LCBiPHN1Yj4yPFwvc3ViPiwgLi4uLCBiPHN1Yj5rPFwvc3ViPilcdWJjZjRcdWIyZTQgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM1NWVcdWMxMWNcdWI3ZWNcdWJhNzQsIGE8c3ViPmk8XC9zdWI+ICZsdDsgYjxzdWI+aTxcL3N1Yj5cdWM2NDAgXHViYWE4XHViNGUwIGombHQ7aVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgYTxzdWI+ajxcL3N1Yj4gPSBiPHN1Yj5qPFwvc3ViPlx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgaVx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzUyNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IklkZWFsIFBhdGgiLCJkZXNjcmlwdGlvbiI6IjxwPk5ldyBsYWJ5cmludGggYXR0cmFjdGlvbiBpcyBvcGVuIGluIE5ldyBMb3N0bGFuZCBhbXVzZW1lbnQgcGFyay4gVGhlIGxhYnlyaW50aCBjb25zaXN0cyBvZiBuIHJvb21zIGNvbm5lY3RlZCBieSBtIHBhc3NhZ2VzLiBFYWNoIHBhc3NhZ2UgaXMgY29sb3JlZCBpbnRvIHNvbWUgY29sb3IgYzxzdWI+aTxcL3N1Yj4uIFZpc2l0b3JzIG9mIHRoZSBsYWJ5cmludGggYXJlIGRyb3BwZWQgZnJvbSB0aGUgaGVsaWNvcHRlciB0byB0aGUgcm9vbSBudW1iZXIgMSBhbmQgdGhlaXIgZ29hbCBpcyB0byBnZXQgdG8gdGhlIGxhYnlyaW50aCBleGl0IGxvY2F0ZWQgaW4gdGhlIHJvb20gbnVtYmVyIG4uPFwvcD5cclxuXHJcbjxwPkxhYnlyaW50aCBvd25lcnMgYXJlIHBsYW5uaW5nIHRvIHJ1biBhIGNvbnRlc3QgdG9tb3Jyb3cuIFNldmVyYWwgcnVubmVycyB3aWxsIGJlIGRyb3BwZWQgdG8gdGhlIHJvb20gbnVtYmVyIDEuIFRoZXkgd2lsbCBydW4gdG8gdGhlIHJvb20gbnVtYmVyIG4gd3JpdGluZyBkb3duIGNvbG9ycyBvZiBwYXNzYWdlcyBhcyB0aGV5IHJ1biB0aHJvdWdoIHRoZW0uIFRoZSBjb250ZXN0YW50IHdpdGggdGhlIHNob3J0ZXN0IHNlcXVlbmNlIG9mIGNvbG9ycyBpcyB0aGUgd2lubmVyIG9mIHRoZSBjb250ZXN0LiBJZiB0aGVyZSBhcmUgc2V2ZXJhbCBjb250ZXN0YW50cyB3aXRoIHRoZSBzYW1lIHNlcXVlbmNlIGxlbmd0aCwgdGhlIG9uZSB3aXRoIHRoZSBpZGVhbCBwYXRoIGlzIHRoZSB3aW5uZXIuIFRoZSBwYXRoIGlzIHRoZSBpZGVhbCBwYXRoIGlmIGl0cyBjb2xvciBzZXF1ZW5jZSBpcyB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlc3QgYW1vbmcgc2hvcnRlc3QgcGF0aHMuPFwvcD5cclxuXHJcbjxwPkFuZHJldyBpcyBwcmVwYXJpbmcgZm9yIHRoZSBjb250ZXN0LiBIZSB0b29rIGEgaGVsaWNvcHRlciB0b3VyIGFib3ZlIE5ldyBMb3N0bGFuZCBhbmQgbWFkZSBhIHBpY3R1cmUgb2YgdGhlIGxhYnlyaW50aC4gWW91ciB0YXNrIGlzIHRvIGhlbHAgaGltIGZpbmQgdGhlIGlkZWFsIHBhdGggZnJvbSB0aGUgcm9vbSBudW1iZXIgMSB0byB0aGUgcm9vbSBudW1iZXIgbiB0aGF0IHdvdWxkIGFsbG93IGhpbSB0byB3aW4gdGhlIGNvbnRlc3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgaW50ZWdlcnMgbiBhbmQgbSAtIHRoZSBudW1iZXIgb2Ygcm9vbXMgYW5kIHBhc3NhZ2VzLCByZXNwZWN0aXZlbHkgKDIgJmxlOyBuICZsZTsgMTAwIDAwMCwgMSAmbGU7IG0gJmxlOyAyMDAgMDAwKS4gVGhlIGZvbGxvd2luZyBtIGxpbmVzIGRlc2NyaWJlIHBhc3NhZ2VzLCBlYWNoIHBhc3NhZ2UgaXMgZGVzY3JpYmVkIHdpdGggdGhyZWUgaW50ZWdlciBudW1iZXJzOiBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4sIGFuZCBjPHN1Yj5pPFwvc3ViPiAtIHRoZSBudW1iZXJzIG9mIHJvb21zIGl0IGNvbm5lY3RzIGFuZCBpdHMgY29sb3IgKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj4gJmxlOyBuLCAxICZsZTsgYzxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLiBFYWNoIHBhc3NhZ2UgY2FuIGJlIHBhc3NlZCBpbiBlaXRoZXIgZGlyZWN0aW9uLiBUd28gcm9vbXMgY2FuIGJlIGNvbm5lY3RlZCB3aXRoIG1vcmUgdGhhbiBvbmUgcGFzc2FnZSwgdGhlcmUgY2FuIGJlIGEgcGFzc2FnZSBmcm9tIGEgcm9vbSB0byBpdHNlbGYuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCBpdCBpcyBwb3NzaWJsZSB0byByZWFjaCB0aGUgcm9vbSBudW1iZXIgbiBmcm9tIHRoZSByb29tIG51bWJlciAxLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBvdXRwdXQgbXVzdCBjb250YWluIGsgLSB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBwYXRoIGZyb20gdGhlIHJvb20gbnVtYmVyIDEgdG8gdGhlIHJvb20gbnVtYmVyIG4uIFRoZSBzZWNvbmQgbGluZSBtdXN0IGNvbnRhaW4gayBudW1iZXJzIC0gdGhlIGNvbG9ycyBvZiBwYXNzYWdlcyBpbiB0aGUgb3JkZXIgdGhleSBtdXN0IGJlIHBhc3NlZCBpbiB0aGUgaWRlYWwgcGF0aC48XC9wPlxyXG4iLCJoaW50IjoiPHA+QSBzZXF1ZW5jZSAoYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4gLCBhPHN1Yj5rPFwvc3ViPikgaXMgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlciB0aGFuIGEgc2VxdWVuY2UgKGI8c3ViPjE8XC9zdWI+LCBiPHN1Yj4yPFwvc3ViPiwgLi4uICwgYjxzdWI+azxcL3N1Yj4pIGlmIHRoZXJlIGV4aXN0cyBpIHN1Y2ggdGhhdCBhPHN1Yj5pPFwvc3ViPiAmbHQ7IGI8c3ViPmk8XC9zdWI+LCBhbmQgYTxzdWI+ajxcL3N1Yj4gPSBiPHN1Yj5qPFwvc3ViPiBmb3IgYWxsIGogJmx0OyBpLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Northeastern European Regional Contest > NEERC 2010 I번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: sgc109