Болашақтың логистикалық компаниясы \(1\) қаладан \(N\) қалаға аса бағалы жүкті жеткізу маршрутын жоспарлауда. Көлік желісі \(N\) қаладан тұрады, олар \(M\) екіжақты жылдамжолмен қосылған. \(i\)-ші жылдамжолмен жүру \(W_i\) минут алады.

Курьердің \(K\) портал заряды бар. Бір зарядты пайдалану кез келген жылдамжолдың бір ұшынан екіншісіне лезде (\(0\) минутта) телепортациялануға мүмкіндік береді. Бір жылдамжолға ең көбі бір заряд жұмсауға болады.

Курьерге \(1\) қаладан \(N\) қалаға ең көбі \(K\) портал зарядын пайдалана отырып жетудің ең аз уақытын анықтауға көмектесіңіз.

Енгізу

Бірінші жолда үш бүтін сан берілген: \(N\), \(M\) және \(K\) (\(2 \le N \le 10^5\), \(1 \le M \le 2 \cdot 10^5\), \(0 \le K \le 20\)).

Келесі \(M\) жолда үштен бүтін сан берілген: \(U_i\), \(V_i\), \(W_i\) — \(i\)-ші жылдамжол қосатын қалалар және жүру уақыты (\(1 \le U_i, V_i \le N\), \(U_i \ne V_i\), \(1 \le W_i \le 10^9\)).

\(1\) қаладан \(N\) қалаға жетуге болатыны кепілденеді. Екі қала арасында бірнеше жылдамжол болуы мүмкін.

Шығару

Жалғыз бүтін санды шығарыңыз — ең аз уақыт (минутпен). Жауап 32-биттік типке сыймауы мүмкін; 64-биттік бүтін санды (long long) қолданыңыз.

Мысалдар

Енгізу 1

4 3 1
1 2 1
2 3 1000
3 4 1

Жауап 1

2

Енгізу 2

3 2 0
1 2 7
2 3 3

Жауап 2

10

Ескертпелер

Мысалдарға түсіндірме

Бірінші мысалда (\(N=4\), \(M=3\), \(K=1\)): \(2\)-\(3\) қырына (салмағы \(1000\)) портал қолданған тиімді, сонда \(1 \to 2 \to 3 \to 4\) жолы \(1 + 0 + 1 = 2\) минут алады.

Екінші мысалда (\(N=3\), \(M=2\), \(K=0\)): портал жоқ, жалғыз жол \(1 \to 2 \to 3\) — \(7 + 3 = 10\) минут.

Ішкі тапсырмалар