using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#define pb push_back
#define oo 0x3f3f3f3f
#define common int m=(l+r)>>1, L=n<<1, 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 poz[Nmax];



void update(int n, int p, int l, int r, int v)
{
	if(l >= r) {H[n]=v;poz[n]=l; return;}
	
	common;
	
	if(p <= m) update(L, l, m, p, v);
	else       update(R, m+1, r, p, v);
	
	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;

for(i=1;i<=N;i++) update(1,i,1,N,d[i]); 


while(nh)
{  
	nh--;
	u=poz[1];
	update(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,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;
}