#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    int v[5001][5001],d[25000], s[25000], inf=1500, poz, min, n, m;

    ifstream f("dijkstra.in");
    f>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;i<=n;j++)
            v[i][j]=1500;


    for(int y=1;y<=m;y++)
    {int i, j, x;
        f>>i>>j>>x;
        v[i][j]=x;
    }

    for(int i=1;i<=n;i++)
        d[i]=v[1][i];

    s[1]=1;

    for(int i=1;i<=n-1;i++)
    {
        min=inf;
        for(int j=1;j<=n;j++)
            if(!s[j] && d[j]<min)
            {
                min=d[j];
                poz=j;
            }
        s[poz]=1;

        for(int j=1;j<=n;j++)
            if(!s[j] && d[j]>d[poz]+v[poz][j])
                d[j]=d[poz]+v[poz][j];

    }

    return 0;
}