#include<fstream>
#include<vector>
#include<queue>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector<pair<int, int> > a[50010];
int d[50010]; // d[i] costul de la nodul sursa(1) pana la nodul i
queue<int> Q;
int n,m;

int main()
{
   f>>n>>m;

   for(int i  =1; i<=m; ++i)
   {
	int x,y,c;
	f>>x>>y>>c;
	
	a[x].push_back(make_pair(y,c));
   }	
   
   d[1] = 1;
   Q.push(1);

   while(!Q.empty())
   {
	int nod = Q.front();
	Q.pop();

	for(auto pr:a[nod])
	{
	    int vec = pr.first;
	    int cost_m = pr.second;
	    
	    if(d[vec] == 0 || d[vec] > d[nod] + cost_m)
	    {
		d[vec] = d[nod] +cost_m;
		Q.push(vec);
            }
	}
   }

   for(int i = 2; i<=n; ++i)
   if(d[i])
	g<<(d[i]-1)<<" ";
   else
	g<<d[i]<<" ";
   g<<"\n";
   

   return 0;
}