#include<fstream>
#include<queue>
#include<vector>
using namespace std;

#define NMAX 50005
#define inf 99999999
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

long n,m,s,d[NMAX],viz[NMAX];


struct cmp{
	bool operator () (long x,long y)
	{ return d[x]<d[y]; }
		  };
		  
struct muchie{
	long x;
	long cost;};


vector <muchie> L[NMAX];
priority_queue <long,vector<long>,cmp> q ;





void dijkstra()
{
long nod;	
	
	s=1;d[s]=0;
	for (long i=2;i<=n;i++)
		d[i]=inf;
	q.push(s);
	viz[s]=1;
	
	while(!q.empty())
		{
    nod=q.top();
    q.pop();	
	viz[nod]=0;
	
	for (long i=0;i<L[nod].size();i++)
		if (!viz[L[nod][i].x] && (d[nod]+L[nod][i].cost < d[ L[nod][i].x ]) )
		  { d[ L[nod][i].x ] = d[nod]+L[nod][i].cost ;
			q.push( L[nod][i].x );
			viz[L[nod][i].x]=1;
		  }
		}
}

int main()
{
	f>>n>>m;
	
	for (long i=1;i<=m;i++)
	{ long x;
	  muchie y;
	  
	  f>>x>>y.x>>y.cost;
	  
	  L[x].push_back(y);
	}

	
	dijkstra();
	
	for (long i=2;i<=n;i++)
		if (d[i]==inf)
		g<<"0 ";
		else
		g<<d[i]<<" ";

	g<<"\n";	
return 0;}