// Dijkstra cu Arbori de intervale
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#define common int m=(l+r)/2, L=2*n, R=L+1
#define oo 0x3f3f3f3f
#define nmax 50005
#define dim 8192
#define pb push_back
struct leg{
int n,c;
};
ofstream fout("dijkstra.out");
vector<leg> G[nmax];

int H[3*nmax],d[nmax],poz[3*nmax],full[3*nmax];

int N,M;
char ax[dim];
int pz;


inline void ci(int &x)
{
	x=0;
	while(ax[pz] <'0' || ax[pz] > '9')
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	while(ax[pz] >= '0' && ax[pz] <= '9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz == dim ) fread(ax,1,dim,stdin),pz=0;
	}
}

void build(int n,int l,int r)
{
    if(l>=r) {H[n]=d[l]; poz[n]=l; full[n]=1; return;}
    common;
    build(L,l,m);
    build(R,m+1,r);

    if(full[L]+full[R]==2 && H[L]==H[R]) full[n]=1;
    else full[n]=0;

    if(H[L]<H[R]) H[n]=H[L], poz[n]=poz[L];
    else H[n]=H[R], poz[n]=poz[R];



}

void update(int n,int ql,int qr,int l,int r,int v)
{
    if(ql<=l && r<=qr)
    {
        H[n]=v;
        poz[n]=l;
        full[n]=1;
        return;

    }

    common;

    if(full[n]==1)
    {
        full[n]=0;
        full[L]=full[R]=1;
        H[L]=H[R]=H[n];

    }

    if(ql<=m) update(L,ql,qr,l,m,v);
    if(qr>=m+1) update(R,ql,qr,m+1,r,v);

    if(full[L]+full[R]==1 && H[L]==H[R]) full[n]=1;
    else full[n]=0;

    if(H[L]<H[R]) H[n]=H[L], poz[n]=poz[L];
    else H[n]=H[R], poz[n]=poz[R];
}
void solve()
{   int i,u;
    vector<leg>::iterator it;
    memset(d,oo,sizeof(d));
    d[1]=0;
    build(1,1,N);
    int nh=N;
    while(nh)
    {
        nh--;
        u=poz[1];
        update(1,u,u,1,N,oo);

        for(it=G[u].begin();it!=G[u].end();it++)
        {
            if(d[it->n]>d[u]+it->c)
            {
                d[it->n]=d[u]+it->c;
                update(1,it->n,it->n,1,N,d[it->n]);
            }

        }
    }


    for(i=2;i<=N;i++)
    {
        if(d[i]==oo) d[i]=0;
        fout<<d[i]<<" ";
    }
}

void cit()
{    int i,x,y,c;
    freopen("dijkstra.in","r",stdin);
    ci(N), ci(M);

    for(i=1;i<=M;i++)
    {
        ci(x), ci(y), ci(c);

        G[x].pb((leg){y,c});


    }


}


int main()
{

    cit();

    solve();
    return 0;
}