pontes09.cpp

#include <iostream>
#include <cstdlib>
#include <cstring>

#define INF 1<<20

using namespace std;

int main() {

    int n, m;
    cin >> n >> m;

    n += 2;
    int c[n][n];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            c[i][j] = INF;

    for(int i = 0; i < m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;

        c[a][b] = c[b][a] = cost;
    }

    int d[n], vis[n], s = 0;
    memset(vis, 0, sizeof vis);

    for(int i = 0; i < n; i++)
        d[i] = c[s][i];

    d[s] = 0;
    vis[s] = 1;

    while (1) {
        int mindist = INF, v;

        for(int i = 0; i < n; i++)
            if(vis[i] == 0 && d[i] < mindist)
                mindist = d[i], v = i;

        if(vis[v])
            break;

        vis[v] = 1;
        for(int i = 0; i < n; i++)
            if(c[v][i] < INF && vis[i] == 0)
                                d[i] = min(d[i], d[v] + c[i][v]);
    }

    cout << d[n-1] << endl;

    return 0;
}