#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("dijkstra.in"); ofstream g("dijkstra.out");
const int MAXN=50005;
const int INF=0x3f3f3f3f;
int n,m,D[MAXN];
bool InQ[MAXN];
vector< pair<int, int> > A[MAXN];
queue <int> Q;
int main()
{   f>>n>>m;
    for(int a,b,c,i=1;i<=m;++i) {f>>a>>b>>c; A[a].push_back(make_pair(b,c));}
    memset(D,INF,sizeof(D));
    Q.push(1); InQ[1]=true;
    while(!Q.empty())
    {   int nod=Q.front(); Q.pop(); InQ[nod]=false;
        vector< pair<int, int> >::iterator it = A[nod].begin(),sf=A[nod].end();
        for(;it!=sf;++it)
            if(D[nod]+it->second < D[it->first])
            {   D[(*it).first]=D[nod]+(*it).second;
                D[(*it).first]=D[nod]+(*it).second;
                if(!InQ[(*it).first]) {Q.push((*it).first); InQ[(*it).first]=true;}
            }
    }
    for(int i=2;i<=n;++i) g<<(D[i]<INF ? D[i] : 0)<<" ";
    g.close(); return 0;
}