시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 23 11 11 47.826%

문제

전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 이에 비례하는 수의 군사가 지나갈 수 있습니다.

Baekjoon World의 국왕은 군사들이 뭉치는 것이 유리하다고 생각해서, 미리 Cube World로 가는 경로를 정해 두고 그 경로로만 모든 군사를 보냈습니다. Baekjoon World의 국왕은 총명해서, 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택했습니다.

그런데 전쟁 때문에 어느 길로 보냈는지에 대한 기록이 불타 없어져 버렸습니다. 전쟁사를 완성하려면 이 기록이 꼭 필요합니다. 위대한 과학자인 당신이 다시 복구해 주세요.

입력

첫 줄에 p와 w가 공백을 사이에 두고 주어집니다. (2 ≤ p ≤ 1 000; 1 ≤ w ≤ 50 000)

다음 줄에 Baekjoon World의 수도 c와 Cube World의 수도 v가 공백을 사이에 두고 주어집니다. (0 ≤ c, v < p; c ≠ v)

다음 w줄에 길이 연결하는 두 지점 wstart, wend,와 길의 너비 wwidth가 공백을 사이에 두고 주어집니다. (0 ≤ wstart, wend < p; wstart ≠ wend; 1 ≤ wwidth ≤ 1 000)

출력

첫 줄에 Baekjoon World의 국왕이 정한 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 출력합니다.

예제 입력 1

7 11
3 5
0 1 15
0 2 23
1 2 16
1 3 27
2 4 3
2 6 21
3 4 14
3 5 10
4 5 50
4 6 9
5 6 42

예제 출력 1

16
W3sicHJvYmxlbV9pZCI6IjExMDg1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZDcwXHVjMGFjIFx1Yzc3NFx1YjNkOSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODA0XHVjN2MxIFx1YjJmOVx1YzJkYyBCYWVram9vbiBXb3JsZFx1Yzc1OCBcdWFkNmRcdWM2NTVcdWM3NDAgQ3ViZSBXb3JsZFx1Yjk3YyBcdWFjZjVcdWFjYTlcdWQ1NjAgXHVjNzkxXHVjODA0XHVjNzQ0IFx1YzEzOFx1YzZiNCBcdWM4MDFcdWM3NzQgXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBCYWVram9vbiBXb3JsZFx1YzY0MCBDdWJlIFdvcmxkXHViMjk0IHBcdWFjMWNcdWM3NTggXHVjOWMwXHVjODEwXHVhY2ZjIHdcdWFjMWNcdWM3NTggXHVhZTM4XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQyOVx1YjJjOFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YWUzOFx1Yzc0MCBcdWM1OTFcdWJjMjlcdWQ1YTVcdWM3NzRcdWJhNzAsIFx1YWMwMSBcdWFlMzhcdWI5YzhcdWIyZTQgXHViMTA4XHViZTQ0XHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzVlYyBcdWM3NzRcdWM1ZDAgXHViZTQ0XHViODQwXHVkNTU4XHViMjk0IFx1YzIxOFx1Yzc1OCBcdWFkNzBcdWMwYWNcdWFjMDAgXHVjOWMwXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkJhZWtqb29uIFdvcmxkXHVjNzU4IFx1YWQ2ZFx1YzY1NVx1Yzc0MCBcdWFkNzBcdWMwYWNcdWI0ZTRcdWM3NzQgXHViYjQ5XHVjZTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM3MjBcdWI5YWNcdWQ1NThcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTc0XHVjMTFjLCBcdWJiZjhcdWI5YWMgQ3ViZSBXb3JsZFx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHViOTdjIFx1YzgxNVx1ZDU3NCBcdWI0NTBcdWFjZTAgXHVhZGY4IFx1YWNiZFx1Yjg1Y1x1Yjg1Y1x1YjljYyBcdWJhYThcdWI0ZTAgXHVhZDcwXHVjMGFjXHViOTdjIFx1YmNmNFx1YjBjOFx1YzJiNVx1YjJjOFx1YjJlNC4gQmFla2pvb24gV29ybGRcdWM3NTggXHVhZDZkXHVjNjU1XHVjNzQwIFx1Y2QxZFx1YmE4NVx1ZDU3NFx1YzExYywgXHVhY2JkXHViODVjIFx1YzBjMVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhZTM4IFx1YzkxMSBcdWIxMDhcdWJlNDRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzg4MVx1Yzc0MCBcdWFlMzhcdWM3NTggXHViMTA4XHViZTQ0XHViOTdjIFx1Y2Q1Y1x1YjMwMFx1ZDY1NFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVkMGRkXHVkNTg4XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZjBcdWIzNzAgXHVjODA0XHVjN2MxIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM1YjRcdWIyOTAgXHVhZTM4XHViODVjIFx1YmNmNFx1YjBjOFx1YjI5NFx1YzljMFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVhZTMwXHViODVkXHVjNzc0IFx1YmQ4OFx1ZDBjMCBcdWM1YzZcdWM1YjRcdWM4MzggXHViYzg0XHViODM4XHVjMmI1XHViMmM4XHViMmU0LiBcdWM4MDRcdWM3YzFcdWMwYWNcdWI5N2MgXHVjNjQ0XHVjMTMxXHVkNTU4XHViODI0XHViYTc0IFx1Yzc3NCBcdWFlMzBcdWI4NWRcdWM3NzQgXHVhZjJkIFx1ZDU0NFx1YzY5NFx1ZDU2OVx1YjJjOFx1YjJlNC4gXHVjNzA0XHViMzAwXHVkNTVjIFx1YWNmY1x1ZDU1OVx1Yzc5MFx1Yzc3OCBcdWIyZjlcdWMyZTBcdWM3NzQgXHViMmU0XHVjMmRjIFx1YmNmNVx1YWQ2Y1x1ZDU3NCBcdWM4ZmNcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIHBcdWM2NDAgd1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICgyICZsZTsgcCAmbGU7IDEgMDAwOyAxICZsZTsgdyAmbGU7IDUwIDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBCYWVram9vbiBXb3JsZFx1Yzc1OCBcdWMyMThcdWIzYzQgY1x1YzY0MCBDdWJlIFdvcmxkXHVjNzU4IFx1YzIxOFx1YjNjNCB2XHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKDAgJmxlOyBjLCB2ICZsdDsgcDsgYyAmbmU7IHYpPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyB3XHVjOTA0XHVjNWQwIFx1YWUzOFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzljMFx1YzgxMCB3PHN1Yj5zdGFydDxcL3N1Yj4sIHc8c3ViPmVuZDxcL3N1Yj4sXHVjNjQwIFx1YWUzOFx1Yzc1OCBcdWIxMDhcdWJlNDQgdzxzdWI+d2lkdGg8XC9zdWI+XHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKDAgJmxlOyB3PHN1Yj5zdGFydDxcL3N1Yj4sIHc8c3ViPmVuZDxcL3N1Yj4gJmx0OyBwOyB3PHN1Yj5zdGFydDxcL3N1Yj4gJm5lOyB3PHN1Yj5lbmQ8XC9zdWI+OyAxICZsZTsgdzxzdWI+d2lkdGg8XC9zdWI+ICZsZTsgMSAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBCYWVram9vbiBXb3JsZFx1Yzc1OCBcdWFkNmRcdWM2NTVcdWM3NzQgXHVjODE1XHVkNTVjIFx1YWNiZFx1Yjg1YyBcdWMwYzFcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWUzOCBcdWM5MTEgXHViMTA4XHViZTQ0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM4ODFcdWM3NDAgXHVhZTM4XHVjNzU4IFx1YjEwOFx1YmU0NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTEwODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcm90ZXN0IiwiZGVzY3JpcHRpb24iOiI8cD5BIGdyb3VwIG9mIG1pbGl0YW50IElUIHN0dWRlbnRzIHdhbnQgdG8gbWFyY2ggZnJvbSB0aGUgQ29tcHV0ZXIgU2NpZW5jZSBidWlsZGluZyB0byB0aGUgdW5pdmVyc2l0eSBWaWNlIENoYW5jZWxsb3ImcnNxdW87cyBvZmZpY2UgdG8gcHJvdGVzdCB0aGUgcmVtb3ZhbCBvZiBCQVNJQyBhcyB0aGUgZmlyc3QteWVhciBwcm9ncmFtbWluZyBsYW5ndWFnZS4gVGhlIHN0dWRlbnRzIHBsYW4gdG8gbWFyY2ggYXJtLWluLWFybSBpbiByb3dzIHRvIHByZXNlbnQgYSB1bmlmaWVkIGZyb250LiBPbmNlIGEgcm93IGxvY2tzIGFybXMsIHRoZXkgd2lsbCBzdGF5IHRoYXQgd2F5IHVudGlsIHRoZWlyIGRlbWFuZHMgYXJlIG1ldC48XC9wPlxyXG5cclxuPHA+VGhlIHByb3Rlc3QgcGxhbm5lcnMgaGF2ZSBtYXBwZWQgb3V0IGFsbCB0aGUgd2Fsa3dheXMgb24gY2FtcHVzIHRvIGZpZ3VyZSBvdXQgaG93IG1hbnkgc3R1ZGVudHMgd2lkZSBlYWNoIHdhbGt3YXkgaXMuIEFsbCB3YWxrd2F5cyBvbiB0aGUgY2FtcHVzIGFsbG93IGZvb3QgdHJhZmZpYyBpbiBib3RoIGRpcmVjdGlvbnMuIFRoZSBwbGFubmVycyBjYW4gc2VlIGZyb20gdGhlIGNhbXB1cyBtYXAgdGhhdCB0aGVyZSBpcyBhIHBhdGggZnJvbSB0aGUgVmljZSBDaGFuY2VsbG9yJnJzcXVvO3Mgb2ZmaWNlIGZyb20gdGhlIENvbXB1dGVyIFNjaWVuY2UgYnVpbGRpbmcgYnV0IHRoZXkgbmVlZCB5b3VyIGhlbHAgd2l0aCB0aGVpciBwbGFucy48XC9wPlxyXG5cclxuPHA+QXMgdGhlIHByb3Rlc3RlcnMmcnNxdW87IGxlYWRpbmcgYWxnb3JpdGhtaXN0IHRoZXkgbmVlZCB5b3UgdG8gZmluZCBhIHBhdGggZnJvbSB0aGUgQ29tcHV0ZXIgU2NpZW5jZSBidWlsZGluZyB0byB0aGUgVmljZSBDaGFuY2VsbG9yJnJzcXVvO3Mgb2ZmaWNlIHRoYXQgbWF4aW1pc2VzIHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMgd2hvIGNhbiB3YWxrIGFybS1pbi1hcm0gZm9yIHRoZSBkdXJhdGlvbiBvZiB0aGUgd2Fsay48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSB0ZXN0IGNhc2UuPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBwICgyICZsZTsgcCAmbGU7IDEgMDAwKSBhbmQgdyAoMSAmbGU7IHcgJmxlOyA1MCAwMDApIHNwZWNpZnlpbmcgdGhlIG51bWJlciBvZiB1bmlxdWUgd2Fsa3dheSBlbmQgcG9pbnRzIGFuZCB0aGUgbnVtYmVyIG9mIHdhbGt3YXlzIG9uIHRoZSB1bml2ZXJzaXR5IGNhbXB1cy48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBjIGFuZCB2ICgwICZsZTsgYywgdiAmbHQ7IHA7IGMgJm5lOyB2KSBiZWluZyB0aGUgd2Fsa3dheSBlbmQgcG9pbnRzIGZvciB0aGUgY29tcHV0ZXIgc2NpZW5jZSBidWlsZGluZyBhbmQgdGhlIHZpY2UgY2hhbmNlbGxvciZyc3F1bztzIG9mZmljZSByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgdyBsaW5lcyBjb250YWluIHRocmVlIGludGVnZXJzIHc8c3ViPnN0YXJ0PFwvc3ViPiwgdzxzdWI+ZW5kPFwvc3ViPiAoMCAmbGU7IHc8c3ViPnN0YXJ0PFwvc3ViPiwgdzxzdWI+ZW5kPFwvc3ViPiAmbHQ7IHA7IHc8c3ViPnN0YXJ0PFwvc3ViPiAmbmU7IHc8c3ViPmVuZDxcL3N1Yj4pIGFuZCB3PHN1Yj53aWR0aDxcL3N1Yj4gKDEgJmxlOyB3PHN1Yj53aWR0aDxcL3N1Yj4gJmxlOyAxIDAwMCkgYmVpbmcgdGhlIHN0YXJ0IGFuZCBlbmQgcG9pbnRzIGZvciBhIHdhbGt3YXkgYW5kIHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMgdGhhdCB3aWxsIGJlIGFibGUgdG8gd2FsayBhcm0taW4tYXJtIGFsb25nIHRoYXQgcGFydGljdWxhciB3YWxrd2F5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIGEgc2luZ2xlIGxpbmUgb3V0cHV0IHRoZSBtYXhpbXVtIG51bWJlciBvZiBzdHVkZW50cyB3aG8gY2FuIHdhbGsgYXJtLWluLWFybSBmcm9tIHRoZSBDb21wdXRlciBTY2llbmNlIGJ1aWxkaW5nIHRvIHRoZSBWaWNlIENoYW5jZWxsb3ImcnNxdW87cyBvZmZpY2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d