3391: 小 W 旅游

小 W 和小 M 正在出国旅游中~他们到的国家共有 n 个城市，由 m 条分别属于 c 家公司的双向路连接。

上图是路线图的一个例子。假设要从车站 A 到车站 D，最短的路线显然是 A → B → D。然而，最短的路线并不意味着最便宜的路线。上图中，铁路 A − B, B − C, C − D 属于同一家铁路公司，而铁路 B − D 属于另一家铁路公司，那么此时路线 A → B → C → D 就可能比路线 A → B → D 便宜。 

这其中的主要原因，就是连续一段属于同一家铁路公司的路线花费并不与长度成正比，通常长度越长单位长度的花费就越少。那么，最终的路线可以被分为若干段，每段都属于同一家铁路公司，总花费就是每段花费之和。

 现在小 W 想知道从 s 城市到 t 城市的最小花费，请问你能帮帮他吗？

若存在从 s 到 t 的路线，则第一行包含一个整数，表示最小花费；否则第一行包含一个整数 −1。

4 4 2 1 4
1 2 2 1
2 3 2 1
3 4 5 1
2 4 4 2
3 2
3 6
10 5	3
100
10 9

54