> #include<cstdio>
> #define min(a,b) a<b?a:b
> int n, m, d[1005], i, j, x[2002], y[2002], z[2002];
> int main()
> {
> 	scanf("%d%d", &m, &n);
> 	for (i = 0; i < m; i++)		scanf("%d%d%d", x + i, y + i, z + i);
> 	for (i = 2; i <= n; i++)    d[i] = 1 << 20;
> 	while (i--)
> 		for (j = 0; j < m; j++)
> 			d[x[j]] = min(d[x[j]], d[y[j]] + z[j]), d[y[j]] = min(d[x[j]] + z[j], d[y[j]]);
> 	printf("%d\n", d[n]);
> }