시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 15 9 9 75.000%

문제

4대강 사업의 성공에 힘입은 정부는 대한민국의 도시들을 모두 운하로 연결하여 뱃길로 KTX를 대체하려는 계획을 세웠다.

대한민국에는 N개의 도시가 있고, 이들을 연결하는 M개의 운하를 건설하려고 한다. 하지만 지형의 문제로 운하의 폭을 제한할 수 밖에 없었기 때문에, 문제가 생겼다. 배의 폭이 운하의 폭보다 작거나 같아야 운하를 무사히 통과할 수 있기 때문이다.

정부는 K개의 노선을 준비했다. 각 노선의 도시 i와 j간을 운행하는 배는 도시 i와 j 간의 경로에 포함되는 운하를 통과할 수 있어야 한다. (이 경로는 여러 개가 존재할 수 있다.) 배가 클수록 많은 사람을 실을 수 있으므로, 정부는 배의 폭을 최대화하기를 원한다.

N개의 도시는 운하로 서로 연결되어 있음이 보장되며, 운하는 양방향으로 통행이 가능하다.

입력

입력의 첫 번째 줄에는 도시의 수 N, 운하의 수 M, 노선의 수 K가 주어진다. (N <= 1000, M <= 100000, K <= 10000)

다음 M개의 줄에는 세 정수 i, j, w가 주어지며, 이는 도시 i와 j 사이에 폭이 w인 운하를 건설할 것임을 의미한다. (1 <= i, j <= N, w <= 200)

다음 K개의 줄에는 각 노선이 연결하는 도시 i, j가 주어진다. (1 <= i, j <= N)

출력

K개의 줄에 각 노선을 운행할 수 있는 최대 배의 폭을 출력한다.

예제 입력 1

6 9 4
1 2 2
1 4 3
1 6 1
2 3 3
2 5 2
3 4 4
3 6 2
4 5 5
5 6 4
2 6
3 5
1 2
4 6

예제 출력 1

3
4
3
4
W3sicHJvYmxlbV9pZCI6IjIzNTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWM2YjRcdWQ1NTgiLCJkZXNjcmlwdGlvbiI6IjxwPjRcdWIzMDBcdWFjMTUgXHVjMGFjXHVjNWM1XHVjNzU4IFx1YzEzMVx1YWNmNVx1YzVkMCBcdWQ3OThcdWM3ODVcdWM3NDAgXHVjODE1XHViZDgwXHViMjk0IFx1YjMwMFx1ZDU1Y1x1YmJmY1x1YWQ2ZFx1Yzc1OCBcdWIzYzRcdWMyZGNcdWI0ZTRcdWM3NDQgXHViYWE4XHViNDUwIFx1YzZiNFx1ZDU1OFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWM1ZWMgXHViYzQzXHVhZTM4XHViODVjJm5ic3A7S1RYXHViOTdjIFx1YjMwMFx1Y2NiNFx1ZDU1OFx1YjgyNFx1YjI5NCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVjMTM4XHVjNmUwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzMDBcdWQ1NWNcdWJiZmNcdWFkNmRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWM3NzRcdWI0ZTRcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IE1cdWFjMWNcdWM3NTggXHVjNmI0XHVkNTU4XHViOTdjIFx1YWM3NFx1YzEyNFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM5YzBcdWQ2MTVcdWM3NTggXHViYjM4XHVjODFjXHViODVjIFx1YzZiNFx1ZDU1OFx1Yzc1OCBcdWQzZWRcdWM3NDQgXHVjODFjXHVkNTVjXHVkNTYwIFx1YzIxOCBcdWJjMTZcdWM1ZDAgXHVjNWM2XHVjNWM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViYjM4XHVjODFjXHVhYzAwIFx1YzBkZFx1YWNiY1x1YjJlNC4gXHViYzMwXHVjNzU4IFx1ZDNlZFx1Yzc3NCZuYnNwO1x1YzZiNFx1ZDU1OFx1Yzc1OCBcdWQzZWRcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YzU0NFx1YzU3YyBcdWM2YjRcdWQ1NThcdWI5N2MgXHViYjM0XHVjMGFjXHVkNzg4IFx1ZDFiNVx1YWNmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHViZDgwXHViMjk0IEtcdWFjMWNcdWM3NTggXHViMTc4XHVjMTIwXHVjNzQ0IFx1YzkwMFx1YmU0NFx1ZDU4OFx1YjJlNC4gXHVhYzAxIFx1YjE3OFx1YzEyMFx1Yzc1OCBcdWIzYzRcdWMyZGMgaVx1YzY0MCBqXHVhYzA0XHVjNzQ0IFx1YzZiNFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWJjMzBcdWIyOTQgXHViM2M0XHVjMmRjIGlcdWM2NDAgaiBcdWFjMDRcdWM3NTggXHVhY2JkXHViODVjXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWM2YjRcdWQ1NThcdWI5N2MgXHVkMWI1XHVhY2ZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHVjNzc0IFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LikgXHViYzMwXHVhYzAwIFx1ZDA3NFx1YzIxOFx1Yjg1ZCBcdWI5Y2VcdWM3NDAgXHVjMGFjXHViNzhjXHVjNzQ0IFx1YzJlNFx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjLCBcdWM4MTVcdWJkODBcdWIyOTQgXHViYzMwXHVjNzU4IFx1ZDNlZFx1Yzc0NCBcdWNkNWNcdWIzMDBcdWQ2NTRcdWQ1NThcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YjI5NCBcdWM2YjRcdWQ1NThcdWI4NWMgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3NGNcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDE4XHViYTcwLCBcdWM2YjRcdWQ1NThcdWIyOTQgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1ZDFiNVx1ZDU4OVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YzIxOCBOLCBcdWM2YjRcdWQ1NThcdWM3NTggXHVjMjE4IE0sIFx1YjE3OFx1YzEyMFx1Yzc1OCZuYnNwO1x1YzIxOCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+KE4gJmx0Oz0gMTAwMCwgTSAmbHQ7PSAxMDAwMDAsIEsgJmx0Oz0gMTAwMDApPFwvc3Bhbj48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggaSwmbmJzcDtqLCB3XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0XHViMjk0IFx1YjNjNFx1YzJkYyBpXHVjNjQwIGogXHVjMGFjXHVjNzc0XHVjNWQwIFx1ZDNlZFx1Yzc3NCB3XHVjNzc4IFx1YzZiNFx1ZDU1OFx1Yjk3YyBcdWFjNzRcdWMxMjRcdWQ1NjAgXHVhYzgzXHVjNzg0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gKDEgJmx0Oz0gaSwgaiAmbHQ7PSBOLCB3ICZsdDs9IDIwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIEtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWIxNzhcdWMxMjBcdWM3NzQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0Jm5ic3A7XHViM2M0XHVjMmRjJm5ic3A7aSwgalx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsdDs9IGksIGogJmx0Oz0gTik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5LXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDEgXHViMTc4XHVjMTIwXHVjNzQ0IFx1YzZiNFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWJjMzBcdWM3NTggXHVkM2VkXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMzUwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFdpZGVzdCBCb2F0cyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gV2F0ZXJsYW5kLCB0aGVyZSBhcmUgTiBsYWtlcyAobnVtYmVyZWQgZnJvbSAxIHRvIG4pIGFuZCBNIGNoYW5uZWxzIGJldHdlZW4gdGhlbS4gVGhlIHdpZHRoIFdpLGogKGluIG1ldGVycykgb2YgZWFjaCBjaGFubmVsIChpLGopIGlzIGtub3duLiBOYXZpZ2F0aW9uIGluIHRoZSBjaGFubmVscyBjYW4gYmUgcGVyZm9ybWVkIGluIGJvdGggZGlyZWN0aW9ucy48XC9wPlxyXG5cclxuPHA+QSB0cmFuc3BvcnRhdGlvbiBjb21wYW55IGhhcyBwcmVwYXJlZCBhIGxpc3Qgb2YgSyBwYWlycyBvZiBsYWtlcywgYW1vbmcgd2hpY2ggd2lsbCBiZSBoZWxkIHJlZ3VsYXIgc2VydmljZXMgd2l0aCBib2F0cyBvZiBwZW9wbGUgYW5kIGdvb2RzLiBUaGVyZSBleGlzdHMgYSBwYXRoIGNvbm5lY3RpbmcgYW55IHR3byBsYWtlcyBpbiBhIHBhaXIgb2YgdGhlIGxpc3QsIGJ1dCBub3QgYWx3YXlzIHRoaXMgcGF0aCBpcyBhIGRpcmVjdCBvbmUsIGkuZS4gdGhpcyBwYXRoIG1heSBwYXNzIHRocnUgb3RoZXIgbGFrZXMuPFwvcD5cclxuXHJcbjxwPldyaXRlIHByb2dyYW0gYm9hdHMgdGhhdCBjYWxjdWxhdGVzIHRoZSBtYXhpbXVtIHdpZHRoIG9mIGJvYXRzLCB3aGljaCBjYW4gcGFzcyBiZXR3ZWVuIHRoZSBwYWlycyBvZiBsYWtlcyBpbiB0aGUgbGlzdCAoYSBib2F0IGNhbiBtb3ZlIGZyb20gb25lIGxha2UgdG8gYW5vdGhlciwgaWYgaXRzIHdpZHRoIGlzIGxlc3MgdGhhbiBvciBlcXVhbCB0byB0aGUgd2lkdGggb2YgdGhlIGNoYW5uZWwsIGNvbm5lY3RpbmcgdGhlIGxha2VzKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBhcmUgZ2l2ZW4gdGhyZWUgaW50ZWdlcnMgTiwgTSBhbmQgSy48XC9wPlxyXG5cclxuPHA+T24gZWFjaCBvbmUgb2YgdGhlIG5leHQgbSBsaW5lcyBhcmUgZ2l2ZW4gdGhyZWUgaW50ZWdlcnMgaSwgaiBhbmQgdywgc2hvd2luZyB0aGF0IHRoZXJlIGlzIGEgY2hhbm5lbCBvZiB3aWR0aCB3IGJldHdlZW4gbGFrZXMgaSBhbmQgaiAoMSAmbGU7IGksIGogJmxlOyBOKS48XC9wPlxyXG5cclxuPHA+VGhlcmUgZm9sbG93IEsgcm93cywgZWFjaCBjb250YWluaW5nIHR3byBsYWtlcyZyc3F1bzsgbnVtYmVycyBpIGFuZCBqLCBiZXR3ZWVuIHdoaWNoIGEgYm9hdCBvZiB0aGUgY29tcGFueSB3aWxsIHRyYXZlbC48XC9wPlxyXG5cclxuPHA+TiAmbGU7IDEwMDAsIE0gJmxlOyAxMDAwMDAsIEsgJmxlOyAxMDAwMCwgV2ksaiAmbGU7IDIwMDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBwcm9ncmFtIHNob3VsZCB3cml0ZSBLIHJvd3Mgb24gdGhlIHN0YW5kYXJkIG91dHB1dCwgZWFjaCBjb250YWluaW5nIG9uZSBpbnRlZ2VyLCBlcXVhbCB0byB0aGUgbWF4aW11bSB3aWR0aCBvZiB0aGUgYm9hdCB0aGF0IGNhbiB0cmF2ZWwgYmV0d2VlbiB0aGUgY29ycmVzcG9uZGluZyB0d28gbGFrZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d