#include <bits/stdc++.h>
#define inf 1000000000
#define pa pair<int,int>
#define mp make_pair
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream f("dijkstra.in"); ofstream g("dijkstra.out");
const int Nmax=50010;
priority_queue <pa> q;
int d[Nmax],viz[Nmax];
vector <pa> v[Nmax];
int main()
{   int n,m;
    f>>n>>m;
    for(int a,b,c,i=1;i<=m;++i) {f>>a>>b>>c; v[a].pb(mp(b,c));}
    for(int i=2;i<=n;i++) d[i]=inf;
    q.push(mp(0,1));
    while(!q.empty())
    {   pa P=q.top(); q.pop();
        int cost=-P.x,nod=P.y;
        if(!viz[nod])
        {   viz[nod]=1;
            vector <pa> :: iterator it=v[nod].begin(),sf=v[nod].end();
            for(;it!=sf; ++it)
            if(d[(*it).x]>cost+(*it).y)
            {   d[(*it).x]=cost+(*it).y;
                q.push(mp(-d[(*it).x],(*it).x));
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(d[i]==inf) g<<"0 "; else g<<d[i]<<' ';
    g.close(); return 0;
}