시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 185 52 36 26.277%

문제

윤이는 유니마을에 거주하는 주민이다. 유니마을은 $1$번부터 $N$번까지 번호가 붙은 $N$개의 건물로 이루어져 있다. 윤이는 그 중 $A$번 건물에 거주하고 있으며, $B$번 건물에 있는 회사로 매일 출퇴근한다.

유니마을은 다음과 같은 구조를 가지고 있다. $N$개의 건물을 잇는 $M$개의 양방향 도로 $R_i$가 있고, 적절한 순서로 도로를 이용하면 임의의 두 건물 사이에 이동이 가능하다. 도로 $R_i$는 서로 다른 $U_i$번 건물과 $V_i$번 건물을 이으며, $R_i$를 거쳐 이동하는 데에는 $T_i$ 만큼의 시간이 소요된다. 한 쌍의 건물을 직접 잇는 도로는 최대 하나이다.

그러던 어느 날, 윤이는 자신이 마법을 쓰면 교통 상황을 바꾸어서 각 도로들을 이동하는데 소모되는 시간을 바꿀 수 있음을 알게 되었다. 윤이는 최대 $K$번 마법을 쓸 수 있는데, 마법을 $k$번 사용하고 나면 모든 $i$에 대해 도로 $R_i$를 이동하는 데 걸리는 시간이 $T_{i, k}$가 된다고 한다. 윤이는 건물에 있을 때만 마법을 사용할 수 있고, 도로를 지나가는 중에 마법을 사용할 수는 없다.

윤이는 마법을 적절히 활용해서 최단 시간으로 회사까지 도착하고자 한다. 윤이를 도와 회사까지 도착하는 데 필요한 최단 시간을 구하시오.

입력

입력의 첫 줄에 $N$과 $M$, 그리고 $A$와 $B$가 주어진다.

다음 $M$개의 줄에 걸쳐 $U_i, V_i, T_i$의 값이 공백을 사이에 두고 주어진다. $(1 \le i \le M)$

다음 줄에 $K$가 주어진다.

다음 $K$개 줄의 $k$번째 줄에는 $T_{1, k}, T_{2, k}, \cdots, T_{M, k}$가 사이에 공백을 두고 주어진다. $(1 \le k \le K)$

출력

윤이가 마법을 적절히 활용했을 때 회사까지 도착하는데 걸리는 최단 시간을 출력한다.

제한

  • $2 \le N \le 1,000$
  • $N-1 \le M \le 2,000$
  • $M \le N(N-1)/2$
  • $1\le A, B, U_i, V_i\le N, A\ne B, U_i \ne V_i$
  • $0 \le K \le 100$
  • $0 \le T_i, T_{i,k} < 10^9$

서브태스크 1 (35점)

$K = 0$

서브태스크 2 (115점)

추가적인 제약 조건이 없다.

예제 입력 1

2 1 2 1
2 1 5
0

예제 출력 1

5

예제 입력 2

3 2 1 3
3 1 5
3 2 5
0

예제 출력 2

5

예제 입력 3

3 2 2 3
3 1 1
1 2 5
2
1 4
5 4

예제 출력 3

5

이 예제는 서브태스크 1의 조건을 만족하지 않는다.

W3sicHJvYmxlbV9pZCI6IjIwMzEzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZDljXHVkMWY0XHVhZGZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjRcdWM3NzRcdWIyOTQgXHVjNzIwXHViMmM4XHViOWM4XHVjNzQ0XHVjNWQwIFx1YWM3MFx1YzhmY1x1ZDU1OFx1YjI5NCBcdWM4ZmNcdWJiZmNcdWM3NzRcdWIyZTQuIFx1YzcyMFx1YjJjOFx1YjljOFx1Yzc0NFx1Yzc0MCAkMSRcdWJjODhcdWJkODBcdWQxMzAgJE4kXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM3NDAgJE4kXHVhYzFjXHVjNzU4IFx1YWM3NFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3MjRcdWM3NzRcdWIyOTQgXHVhZGY4IFx1YzkxMSAkQSRcdWJjODggXHVhYzc0XHViYjNjXHVjNWQwIFx1YWM3MFx1YzhmY1x1ZDU1OFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAsICRCJFx1YmM4OCBcdWFjNzRcdWJiM2NcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDY4Y1x1YzBhY1x1Yjg1YyBcdWI5ZTRcdWM3N2MgXHVjZDljXHVkMWY0XHVhZGZjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWIyYzhcdWI5YzhcdWM3NDRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFkNmNcdWM4NzBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gJE4kXHVhYzFjXHVjNzU4IFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWM3ODdcdWIyOTQgJE0kXHVhYzFjXHVjNzU4IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWMgJFJfaSRcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWM4MDFcdWM4MDhcdWQ1NWMgXHVjMjFjXHVjMTFjXHViODVjIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWJhNzQgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjQ1MCBcdWFjNzRcdWJiM2MgXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc3NFx1YjNkOVx1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1YjNjNFx1Yjg1YyAkUl9pJFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4ICRVX2kkXHViYzg4IFx1YWM3NFx1YmIzY1x1YWNmYyAkVl9pJFx1YmM4OCBcdWFjNzRcdWJiM2NcdWM3NDQgXHVjNzc0XHVjNzNjXHViYTcwLCAkUl9pJFx1Yjk3YyBcdWFjNzBcdWNjZDAgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YjM3MFx1YzVkMFx1YjI5NCAkVF9pJCBcdWI5Y2NcdWQwN2NcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzE4Y1x1YzY5NFx1YjQxY1x1YjJlNC4gXHVkNTVjIFx1YzMwZFx1Yzc1OCBcdWFjNzRcdWJiM2NcdWM3NDQgXHVjOWMxXHVjODExIFx1Yzc4N1x1YjI5NCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2VjXHViMzU4IFx1YzViNFx1YjI5MCBcdWIwYTAsIFx1YzcyNFx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHViOWM4XHViYzk1XHVjNzQ0IFx1YzRmMFx1YmE3NCBcdWFkNTBcdWQxYjUgXHVjMGMxXHVkNjY5XHVjNzQ0IFx1YmMxNFx1YWZiOFx1YzViNFx1YzExYyBcdWFjMDEgXHViM2M0XHViODVjXHViNGU0XHVjNzQ0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWMxOGNcdWJhYThcdWI0MThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YzcyNFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgJEskXHViYzg4IFx1YjljOFx1YmM5NVx1Yzc0NCBcdWM0ZjggXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViOWM4XHViYzk1XHVjNzQ0ICRrJFx1YmM4OCZuYnNwO1x1YzBhY1x1YzZhOVx1ZDU1OFx1YWNlMCBcdWIwOThcdWJhNzQgXHViYWE4XHViNGUwICRpJFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViM2M0XHViODVjICRSX2kkXHViOTdjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCAkVF97aSwga30kXHVhYzAwIFx1YjQxY1x1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzcyNFx1Yzc3NFx1YjI5NCBcdWFjNzRcdWJiM2NcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1YjljYyBcdWI5YzhcdWJjOTVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTQgXHVjOTExXHVjNWQwIFx1YjljOFx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzI0XHVjNzc0XHViMjk0IFx1YjljOFx1YmM5NVx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVkNjVjXHVjNmE5XHVkNTc0XHVjMTFjIFx1Y2Q1Y1x1YjJlOCBcdWMyZGNcdWFjMDRcdWM3M2NcdWI4NWMgXHVkNjhjXHVjMGFjXHVhZTRjXHVjOWMwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuIFx1YzcyNFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVkNjhjXHVjMGFjXHVhZTRjXHVjOWMwIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YjI5NCBcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YjJlOCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDAgJE4kXHVhY2ZjICRNJCwgXHVhZGY4XHViOWFjXHVhY2UwICRBJFx1YzY0MCAkQiRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJE0kXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgJFVfaSwgVl9pLCBUX2kkXHVjNzU4IFx1YWMxMlx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlIGkgXFxsZSBNKSQ8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCAkSyRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJEskXHVhYzFjIFx1YzkwNFx1Yzc1OCAkayRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICRUX3sxLCBrfSwgVF97Miwga30sIFxcY2RvdHMsIFRfe00sIGt9JFx1YWMwMCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMSBcXGxlIGsgXFxsZSBLKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3MjRcdWM3NzRcdWFjMDAgXHViOWM4XHViYzk1XHVjNzQ0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWQ2NWNcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjIFx1ZDY4Y1x1YzBhY1x1YWU0Y1x1YzljMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMiZuYnNwO1xcbGUgTiBcXGxlIDEsMDAwJDxcL2xpPlxyXG5cdDxsaT4kTi0xIFxcbGUgTSBcXGxlIDIsMDAwJDxcL2xpPlxyXG5cdDxsaT4kTSBcXGxlIE4oTi0xKVwvMiQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlIEEsIEIsIFVfaSwgVl9pXFxsZSBOLCBBXFxuZSBCLCBVX2kgXFxuZSBWX2kkPFwvbGk+XHJcblx0PGxpPiQwIFxcbGUgSyBcXGxlIDEwMCQ8XC9saT5cclxuXHQ8bGk+JDAgXFxsZSBUX2ksIFRfe2ksa30gJmx0OyAxMF45JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kSyA9IDAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD5cdWNkOTRcdWFjMDBcdWM4MDFcdWM3NzggXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPlx1Yzc3NCBcdWM2MDhcdWM4MWNcdWIyOTQgXHVjMTFjXHViZTBjXHVkMGRjXHVjMmE0XHVkMDZjIDFcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjAzMTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb21tdXRlIiwiZGVzY3JpcHRpb24iOiI8cD5ZdW5lZSBpcyBhIHJlc2lkZW50IG9mIFVOSS10b3duLiBVTkktdG93biBjb25zaXN0cyBvZiAkTiQgYnVpbGRpbmdzLCBudW1iZXJlZCBmcm9tICQxJCB0byAkTiQuIFl1bmVlIGxpdmVzIGluIGJ1aWxkaW5nICRBJCZuYnNwO2FuZCBjb21tdXRlcyB0byB0aGUgY29tcGFueSZuYnNwO2luJm5ic3A7YnVpbGRpbmcgJEIkJm5ic3A7ZXZlcnkgZGF5LjxcL3A+XHJcblxyXG48cD5JbiBVTkktdG93biwgdGhlcmUgYXJlICRNJCBiaWRpcmVjdGlvbmFsIHJvYWRzICRSX2kkLCBlYWNoIGNvbm5lY3RpbmcgYSBwYWlyIG9mIGJ1aWxkaW5ncy4gSXQgaXMgcG9zc2libGUgdG8gbW92ZSBmcm9tIGFueSBvbmUgYnVpbGRpbmcgdG8gYW55IG90aGVyIHVzaW5nJm5ic3A7b25lIG9yIG1vcmUgcm9hZHMuIFJvYWQgJFJfaSQgY29ubmVjdHMgdHdvIGRpZmZlcmVudCBidWlsZGluZ3MgJFVfaSQgYW5kICRWX2kkLCBhbmQgaXQgdGFrZXMgdGltZSAkVF9pJCB0byB0cmF2ZWwgdGhlIHJvYWQgJFJfaSQuIEZvciBlYWNoIHBhaXIgb2YgYnVpbGRpbmdzLCB0aGVyZSBpcyBhdCBtb3N0IG9uZSByb2FkIGNvbm5lY3RpbmcgdGhlbS48XC9wPlxyXG5cclxuPHA+T25lIGRheSwgWXVuZWUgcmVhbGl6ZWQgdGhhdCB0aGV5IGNhbiB1c2UgbWFnaWMgdG8gY29udHJvbCB0aGUgdHJhZmZpYywgd2hpY2ggY2hhbmdlcyB0aGUgdGltZSBpdCB0YWtlcyZuYnNwO3RvIHRyYXZlbCBlYWNoIHJvYWQuIFl1bmVlIGNhbiB1c2UgdGhlaXIgbWFnaWMgYXQgbW9zdCAkSyQgdGltZXMuIEFmdGVyIHVzaW5nIHRoZSZuYnNwO21hZ2ljJm5ic3A7JGskIHRpbWVzIGluIHRvdGFsLCB0aGUgdGltZSBpdCB0YWtlcyZuYnNwO3RvIHRyYXZlbCB0aGUgcm9hZCAkUl9pJCBjaGFuZ2VzIHRvJm5ic3A7JFRfe2ksIGt9JC4gWXVuZWUgY2FuIG9ubHkgdXNlIHRoZWlyIG1hZ2ljIGluIGEgYnVpbGRpbmc7IHRoZXkgY2Fubm90IHVzZSBpdCB3aGlsZSB0cmF2ZWxpbmcgYSByb2FkLjxcL3A+XHJcblxyXG48cD5ZdW5lZSB3YW50cyB0byBnZXQgdG8mbmJzcDt0aGVpciBjb21wYW55IGluIHRoZSBzaG9ydGVzdCB0aW1lIGJ5IHByb3Blcmx5IHV0aWxpemluZyB0aGVpciZuYnNwO21hZ2ljLiBIZWxwIFl1bmVlIHRvIGZpbmQgdGhlIG1pbmltdW0gdGltZSByZXF1aXJlZCB0byByZWFjaCB0aGUgY29tcGFueS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIHRoZSBmaXJzdCBsaW5lLCAkTiQsICRNJCwgJEEkLCBhbmQgJEIkIGFyZSBnaXZlbi48XC9wPlxyXG5cclxuPHA+VGhlICRpJC10aCBsaW5lIG9mIHRoZSBuZXh0ICRNJCBsaW5lcyBjb250YWlucyAkVV9pLCBWX2ksIFRfaSQsIHNlcGFyYXRlZCBieSB3aGl0ZXNwYWNlLiZuYnNwOyQoMSBcXGxlIGkgXFxsZSBNKSQ8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyAkSyQuPFwvcD5cclxuXHJcbjxwPlRoZSAkayQtdGggbGluZSBvZiB0aGUgbmV4dCAkSyQgbGluZXMgY29udGFpbnMmbmJzcDskVF97MSwga30sIFRfezIsIGt9LCBcXGNkb3RzLCBUX3tNLCBrfSQsIHNlcGFyYXRlZCBieSB3aGl0ZXNwYWNlLiZuYnNwOyQoMSBcXGxlIGsgXFxsZSBLKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gdGltZSByZXF1aXJlZCB0byByZWFjaCB0aGUgY29tcGFueSBieSBwcm9wZXJseSB1dGlsaXppbmcgWXVuZWUmIzM5O3MgbWFnaWMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMiZuYnNwO1xcbGUgTiBcXGxlIDEsMDAwJDxcL2xpPlxyXG5cdDxsaT4kTi0xIFxcbGUgTSBcXGxlIDIsMDAwJDxcL2xpPlxyXG5cdDxsaT4kTSBcXGxlIE4oTi0xKVwvMiQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlIEEsIEIsIFVfaSwgVl9pXFxsZSBOLCBBXFxuZSBCLCBVX2kgXFxuZSBWX2kkPFwvbGk+XHJcblx0PGxpPiQwIFxcbGUgSyBcXGxlIDEwMCQ8XC9saT5cclxuXHQ8bGk+JDAgXFxsZSBUX2ksIFRfe2ksa30gJmx0OyAxMF45JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kSyA9IDAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzLjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzMiOiI8cD5Ob3RlIHRoYXQgdGhpcyBzYW1wbGUgZGF0YSBkb2VzIG5vdCBzYXRpc2Z5IHRoZSBjb25kaXRpb24gZm9yIHN1YnRhc2sgMS48XC9wPlxyXG4ifV0=

채점 및 기타 정보

  • 예제는 채점하지 않는다.