#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define inf 1000000002
int n,m,x,y,viz[50002],start[50002],nrc,cost,d[50002],coada[50002],pr,ul,nr,k;
struct nod
{
    int vecin,cost,leg;
}L[250002];

int main()
{
    fin>>n >> m;
    k=0;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y >> cost;
        k++;
        L[k].vecin=y;
        L[k].cost=cost;
        L[k].leg=start[x];
        start[x]=k;
    }
    for (int j = 1; j <= n; ++j) {
        d[j]=inf;
    }
    d[1]=0;
    coada[1]=1;
    pr=1;
    ul=1;
    nr=1;
    viz[1]=1;
    while(nr>0){
        x=coada[pr];
        for (int i = start[x]; i!=0; i=L[i].leg) {
            y=L[i].vecin;
            if(d[y]>d[x]+L[i].cost){
                d[y]=d[x]+L[i].cost;
                if(viz[y]==0){
                    ul++;
                    if(ul>n){
                        ul=1;
                    }
                    coada[ul]=y;
                    viz[y]=1;
                    nr++;
                }
            }
        }
        pr++;
        viz[x]=0;
        if(pr>n){
            pr=1;
        }
        nr--;
    }
    for (int i = 2; i <= n; ++i) {
        if(d[i]==inf){
            fout << "0 ";
        }else fout << d[i] << " ";
    }

    return 0;
}