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

using namespace std; 

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

const int oo = 0x3f3f3f3f, MAXN = 50001;
vector<pair <int, int> > G[MAXN]; 

int N, M, d[MAXN]; 
bool viz[MAXN];

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

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

void Dijkstra() 
{
	memset(d, oo, sizeof (d));
	
	for (d[1] = 0, Heap.push (viz[1] = 1); ! Heap.empty (); )
	{
		int U = Heap.top(); viz[U] = 0;
		Heap.pop();
		
		for(vector< pair <int, int> > :: iterator it = G[U].begin(); it!=G[U].end(); ++it) 
		{
			if( d[U] + it -> second < d[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; 
}