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

#define MAX 50001
#define LIM 1001

using namespace std;

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

inline void dij(int nod)
{
    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)
        {
            c[D[(*it).first]].erase((*it).first);
            D[(*it).first]=D[nod]+(*it).second;
            c[D[(*it).first]].insert((*it).first);
        }
}

inline int next()
{
    int i,x;

    for(i=1;i<=C;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;

    C=0;
    for(i=1;i<=M;i++)
    {
        in>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
        if(z>C) C=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++)
        out<<D[i]<<' ';
    out<<D[N]<<'\n';

    out.close();
}