单源最短路
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1005;
#define INF 0x7fffffffint data[N][N];
int lowc[N];
bool vis[N];
int n, m;
void djst(int p) {for(int i = 1; i <= n; i++) {lowc[i] = data[p][i];vis[i] = false;}vis[p] = true;int i, j;for(i = 1; i <= n-1; i++) {int minv = INF, c = 0;for(j = 1; j <= n; j++) {if(!vis[j] && lowc[j] < minv) {minv = lowc[j];c = j;}}if(c == 1) {printf("%d\n", minv); return;}vis[c] = true;for(j = 1; j <= n; j++) {if(!vis[j] && data[c][j] != INF && minv + data[c][j] < lowc[j]) {lowc[j] = minv + data[c][j];}}}
}
int main() {cin >> m >> n;for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {data[i][j] = INF;}}int u, v, w;for(int i = 0; i < m; i++) {cin >> u >> v >> w;if(w < data[u][v]) {data[u][v] = w;data[v][u] = w;}}djst(n);return 0;
}