描述

有$N$个岛屿，记为1、2、3、...、N。有$M$座巨大弹弓，瞄准了另外一个岛屿，并且由于需要精密计算，目标岛屿不能更改。每个岛屿可以安装多个弹弓。

弹弓网络在使用一段时间以后，已经能稳定的运作，所以弹弓公司开始对弹弓寄送征收费用。由于不同岛屿上的物价、地形、风向、人员成本都不一样，定价也不尽相同。除了列出每个弹弓的起点和终点，还给出了弹弓的邮费。

现在你在1号岛屿，需要利用这些弹弓把包裹寄到$K$号岛屿，问，能否到达？如果能，请找出最少需要使用多少费用，如果不能，请输出-1.

输入输出格式

输入

第一行为两个以空格隔开的正整数$N$ $K$， 其中$N$表示一共有几个岛屿，$K$表示包裹的目的地岛屿编号。 ( $1≤K≤N<1,000$ )

第二行为一个正整数$M$，表示一共有多少座弹弓。 ( $1 ≤ M ≤ 50,000$ )

随后$M$行，每行为三个以空格分割的正整数$a$ $b$ $p$，表示$a$岛屿上有一个瞄准了$b$岛屿的弹弓，每次弹射需要支付$p$费用。 ( $1 ≤ a ≤ N, 1 ≤ b ≤ N, 1 ≤ p ≤ 100,000$ )

输出

一行，一个整数，如果能到达，则输出最少需要使用的费用，否则输出-1。

样例

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

3

样例一说明

有两条路径可以到达3号岛屿

• 1->2->3 共花费6
• 1->2->4->3 共花费3

第二条路径的花费更低，所以输出3