#include <iostream>
#include <fstream>
#include <vector>
#define INF 20000001
#define noduri 20001
using namespace std;
int n,m,c[noduri][noduri];
vector<int> D,S,T;
void Read()
{
    ifstream f("dijkstra.in");
    f>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        if(i==j)
            c[i][j]=0;
        else c[i][j]=INF;
    }
    int x,y,cost;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        c[x][y]=cost;
    }
    D.resize(n);
    S.resize(n);
    T.resize(n);
}

int find_k_min()
{
    int k,kmin=0,minim=INF;
    for(k=1;k<=n;k++)
        if(!S[k]&&D[k]<minim)
    {
        minim=D[k];
        kmin=k;
    }
    return kmin;
}
void initialise()
{
    int R=1;
    S[R]=1;
    for(int x=2;x<=n;x++)
    {
        D[x]=c[R][x];
        if(D[x]!=INF)
            T[x]=R;
    }
}

void Dijkstra()
{
    int k;
    k=find_k_min();
    while(k)
    {
        S[k]=1;
        for(int x=1;x<=n;x++)
            if(!S[x]&&D[k]+c[k][x]<D[x])
        {
            D[x]=D[k]+c[k][x];
            T[x]=k;
        }
        k=find_k_min();
    }
}
void Write()
{
    ofstream g("dijkstra.out");
        for(int x=2;x<=n;x++)
            g<<D[x]<<" ";
}
int main()
{
    Read();
    initialise();
    Dijkstra();

    return 0;
}