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

using namespace std; 

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

int N, M, viz[50001], oo = 0x3f3f3f3f, d[50001]; 

vector<pair <int, int> > G[50001]; 

struct compare
{
	bool operator () (const int &N1, const int &N2) 
	{
	return d[N1] > d[N2];
	}	
};

priority_queue<int, vector<int>, compare > Heap; 

void Dijkstra() 
{
	memset(d, oo, sizeof(d));
	
	d[1] = 0; 
	Heap.push(1); 
	viz[1] = 1; 
	
	while(!Heap.empty()) 
	{
		int U = Heap.top(); 
		Heap.pop();
		
		for(vector< pair <int, int> > :: iterator it = G[U].begin(); it!=G[U].end(); ++it) 
		{
			if( d[U] + it -> second < it -> first) 
				{
					d[it->first] = d[U] + it -> second; 
					if(viz[it -> first] == 0) 
					{
						Heap.push(it ->first); 
						viz[it -> first] = 1; 
					}
			}
		}
	}
}
			
	
int main() 
{
	int i,x,y,c;
	in >> N >> M; 
	
	for(i = 1; i <= M; i++) 
	{
		in >> x >> y >> c; 
		G[x].push_back(make_pair(y,c)); 
	}
	
	Dijkstra(); 
	
	for(i = 2; i <= N; i++) 
		if(d[i] < oo) 
			out << d[i] <<" "; 
		else out << "0 "; 
		
		return 0; 
}