У мрежи рачунара сигнал креће од једног почетног рачунара и креће се посредством канала комуникације до свих других рачунара који су непосредно или посредно (преко других рачунара) повезани са почетним. Ако су познате везе између рачунара и време потребно да сигнал пређе преко сваке везе, написати програм који одређује колико је времена потребно да сигнал стигне до свих рачунара у мрежи.

Улаз

Са стандардног улаза се уноси број рачунара \(n\) (\(1 \leq n \leq 1000\)), затим број комуникационих канала \(m\) (\(1 \leq m \leq n^2\)) а затим и опис сваког (једносмерног) комуникационог канала у облику три цела броја (два броја од \(1\) до \(n\) који описују од ког до ког рачунара води канал и затим цео број од \(1\) до \(1000\) који описује колико је времена потребно да сигнал прође комуникационим каналом). На крају се уноси и цео број \(s\) (\(1 \leq s \leq n\)) који представља број рачунара од ког сигнал креће.

Излаз

На стандардни излаз исписати најмање време потребно да сви рачунари приме сигнал или \(-1\), ако постоји неки рачунар до ког сигнал не може да дође.

Пример

Улаз

5 7
1 2 7
1 3 3
1 5 6
2 1 2
3 5 2
4 2 3
5 4 1
1

Излаз

7

Објашњење

На слици су приказани рачунари, везе између њих и времена потребна да сигнал дође од рачунара 1 до осталих рачунара. На пример, сигнал до рачунара 5 може да стигне за 5 јединица времена, ако иде преко рачунара 3 (директном везом било би потребно 6 јединица времена). Са друге стране, до рачунара 2 најбоље је да сигнал иде директном везом (пут преко рачунара 3, 5 и 4 захтевао би 9 јединица времена). После 7 јединица времена сигнал је стигао до свих рачунара.