using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#define pb push_back
#define oo 0x3f3f3f3f
#define common int m=(l+r)/2, L=n*2, R=L+1
#define nmax 50005
#define Nmax 150005

struct leg{
	int n,c;
};

vector<leg> G[nmax];
ofstream fout("dijkstra.out");
int N,M,nh;
int d[50005];
int H[Nmax];
int full[Nmax];
int poz[Nmax];

void build(int n,int l,int r)
{
	if(l>=r) {H[n]=d[l]; full[n]=1; poz[n]=l;

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[R],poz[n]=poz[R]; 
	else H[n]=H[L], poz[n]=poz[L];
		
	
	
	
}


void update(int n,int ql,int qr,int l,int r, int v )
{
	if(ql<=l && r<=qr)
	{
		H[n]=v;
		full[n]=1;
		poz[n]=l;
		return;
	}		
	common;
	
	if(full[n])
	{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]==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 solve()
{int u,i;
vector<leg>::iterator it;
nh=N;
memset(d, oo, sizeof(d));
d[1]=0;

build(1,1,N);

while(nh)
{  
	nh--;
	u=poz[1];
	update(1,poz[1],poz[1],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;
	
	ifstream fin("dijkstra.in");
	
	fin>>N>>M;
	for(i=2;i<=N;i++) 
		  d[i]=oo;
	d[1]=0;
	
	for(i=1;i<=M;i++)
	{	
		fin>>x>>y>>c;
		G[x].pb((leg){y,c});
    }
    
	fin.close();
}
int main()
{
	
	cit();
	solve();
	
	fout.close();
	return 0;
}