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

#define Nmax 50005
#define inf 1000000

vector <pair<int,int> > G[Nmax];
int cost[Nmax];
int n;

void citire()
{
	int i, m, x,y,c;
	ifstream f("dijkstra.in");
	 f>>n>>m;
	 
	 for(i=0;i<m;i++)
	 {
		f>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
		
	 }
	 
	fclose(stdin);
}

void dijkstra()
{
  vector< pair<int, int> > ::iterator it,sfarsit;
	int nod,primul;
 queue<int>Q;
 bool viz[Nmax];
 
  memset(cost,inf,sizeof(cost));
  memset(viz,false, sizeof(viz));
 
  viz[1]=true;
  cost[1]=0;
  Q.push(1);
  
  while(!Q.empty())
  {
	nod=Q.front();
	Q.pop();
	viz[nod]=false;
	sfarsit=G[nod].end();
  for(it=G[nod].begin();it!=sfarsit;it++)
  {
	  primul=it->first;
	if(cost[nod]+it->second<cost[primul])
	{
		cost[primul]=cost[nod]+it->second;
	    if(!viz[primul])
	     {
	       Q.push(primul);
	       viz[primul]=true;
	     }
	}
    }
  }
}

void afisare()
{
	int i;
	ofstream g("dijkstra.out");
     for(i=2;i<=n;i++)
        if(cost[i]<inf)
         g<<cost[i]<<"\n";
        else		
		  g<<0<<" ";
		
	g.close();
}

int main()
{
	citire();
	dijkstra();
	afisare();
	return 0;
}