#include<fstream>
#include<vector>
#define inf 2000000000
using namespace std;
int n, m, i, x, y, z, h[50003], p[50003], dh, k, p1, s, D[50003], aux, vecin, cost, upOrIns;
vector< pair<int, int> > L[50003];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int main()
{
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y>>z;
        L[x].push_back(make_pair(y, z));
    }
    for(i=2; i<=n; i++)
        D[i]=inf;
    h[1]=1;
    p[1]=1;
    dh=1;
    while(dh!=0)
    {
        k=h[1];
        h[1]=h[dh];
        dh--;
        p1=1;
        s=2;
        while(s<=dh)
        {
            if(s+1<=dh && D[h[s+1]]<D[h[s]])
                s++;
            if(D[h[s]]<D[h[p1]])
            {
                aux=h[s];
                h[s]=h[p1];
                h[p1]=aux;
                p[h[s]]=s;
                p[h[p1]]=p1;
                p1=s;
                s*=2;
            }
            else
                break;
        }
        p[k]=-1;
        for(i=0; i<L[k].size(); i++)
        {
            vecin=L[k][i].first;
            cost=L[k][i].second;
            if(D[vecin]>D[k]+cost)
                D[vecin]=D[k]+cost;
            if(p[vecin]!=0)
                upOrIns=p[vecin];
            else
            {
                dh++;
                h[dh]=vecin;
                p[vecin]=dh;
                upOrIns=dh;
            }
            if(D[h[upOrIns]]<D[h[upOrIns/2]])
            {
                s=upOrIns;
                p1=s/2;
                while(p1>0 && D[h[s]]<D[h[p1]])
                {
                    aux=h[s];
                    h[s]=h[p1];
                    h[p1]=aux;
                    p[h[s]]=s;
                    p[h[p1]]=p1;
                    s=p1;
                    p1/=2;
                }
            }
            else
            {
                p1=upOrIns;
                s=2*p1;
                while(s<=dh)
                {
                    if(s+1<=dh && D[h[s+1]]<D[h[s]])
                        s++;
                    if(D[h[s]]<D[h[p1]])
                    {
                        aux=h[s];
                        h[s]=h[p1];
                        h[p1]=aux;
                        p[h[s]]=s;
                        p[h[p1]]=p1;
                        p1=s;
                        s*=2;
                    }
                    else
                        break;
                }

            }
        }
    }
    for(i=2; i<=n; i++)
        D[i]!=inf?out<<D[i]<<" ":out<<"0 ";
}