#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>

#define MAX 50001
#define LIM 5001

using namespace std;

vector <pair<int,int> > v[MAX];
set <int> c[LIM];
int D[MAX],T[MAX];

inline void dij(int nod)
{
    int x,y;
    vector <pair<int,int> >::iterator it;
    for(it=v[nod].begin();it!=v[nod].end();it++)
        if(D[(*it).first]==-1||D[(*it).first]>D[nod]+(*it).second)
        {
            x=(*it).first;
            y=(*it).second;
            if(D[x]!=-1) c[D[x]].erase(x);
            D[x]=D[nod]+y;
            c[D[x]].insert(x);
        }
}

inline int next()
{
    int i,x;

    for(i=1;i<LIM;i++)
        if(c[i].size()!=0)
        {
            x=*c[i].begin();
            c[i].erase(*c[i].begin());
            return x;
        }
    return -1;
}

int main()
{
    int M,N,x,y,z,i,S;

    ifstream in;
    in.open("dijkstra.in");

    in>>N>>M;

    for(i=1;i<=M;i++)
    {
        in>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }

    in.close();

    memset(D,-1,sizeof(D));
    D[1]=0;
    memset(T,0,sizeof(T));

    S=1;
    while(S>0)
    {
        dij(S);
        S=next();
    }

    ofstream out;
    out.open("dijkstra.out");

    for(i=2;i<N;i++)
        if(D[i]!=-1) out<<D[i]<<' ';
        else out<<"0 ";
    if(D[N]!=-1) out<<D[N]<<'\n';
    else out<<"0\n";

    out.close();
}