阿兩買醬酒

題目敘述

阿兩家裡的醬酒用完了，正準備騎腳踏車出門買醬酒的時候，接到了大家討債的電話。阿兩所在的城市由 $N$ 間房屋所組成，編號是 $0$ 到 $N-1$ ，一共有 $N-1$ 個人要討債，這 $N-1$ 個人各在其中的一個房屋裡；由於最近在整頓交通，城市中只有 $M$ 條單向的道路可以通行，經過每條道路都需要一些時間。

由於阿兩欠債已久，每個人都想要再多收利息，在房屋編號 $i$ 的人所收的利息等於他們打完電話之後等待的時間(秒)乘上房屋的編號 $i$。對於那些阿兩沒有辦法前往他們房子的人，他們決定等路修好之後再收錢，因此他們不會收取利息。 阿兩在收到電話之後立刻派出了 $N-1$ 臺獨立行動的機器人替他還錢，請問阿兩最少需要繳多少利息呢？

輸入說明

第一行有兩個數字 $N,M$ 表示有 $N$ 間房屋， $M$ 條連接房屋的單向道路，房屋的編號為 $0,1,2,...,N-1$。接下來有 $M$ 行，每行有三個整數 $A,B,C$ 表示間有一條從 $A$ 房間到 $B$ 房間的單向道路，通過它的時候需要花 $C$ 秒的時間。 最後有一個數字 $s$，代表阿兩所在的房屋編號。
其中 $0\leq A,B\leq N-1, 0\leq C \leq 10^7$ 。

輸出說明

請輸出阿兩需要付多少利息，由於金額可能很大，請輸出模 $10^9+7$ 之後的值。

範例輸入1

4 5
2 0 2
2 1 6
2 3 10
0 3 3
1 3 7
2

範例輸出1

21

範例輸入2

4 4
3 2 5
1 2 7
0 2 3
1 0 2
1

範例輸出2

10

配分方法

• 30% $1 \leq N \leq 100$, $1 \leq M \leq 1000$
• 60% $1 \leq N \leq 10^3$, $1 \leq M \leq 10^5$
• 100% $1 \leq N \leq 10^5$, $1 \leq M \leq 10^6$

Hints

備註

Judge Setting