#include<fstream> 
#include<vector> 
#include<queue>
#include<cstring>
#define INF 0x3f3f3f3f 
#define NMAX 50002
using namespace std; 

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

int N, M, dist[NMAX], cnt_Q[NMAX];
bool in_Q[NMAX], ciclu_negativ;

vector<int > G[NMAX], C[NMAX]; 

/*struct comp
{
	bool operator() (const int &A, const int &B) 
	{
		return dist[A] > dist[B]; 
	}
}; 

priority_queue< int, vector<int>, comp > Q; */
queue<int > Q;


void solve() 
{
	memset(dist, INF, sizeof(dist));
	
	Q.push(1);
	dist[1] = 0;
	in_Q[1] = true; 
	
	while(!Q.empty() && !ciclu_negativ) 
	{
		int nod = Q.front(); 
		Q.pop(); 
		in_Q[nod] = false; 
		
		for(int i = 0; i < G[nod].size(); ++i) 
			{
				if(dist[G[nod][i]] > dist[nod] + C[nod][i]) 
				{
					dist[G[nod][i]] = dist[nod] + C[nod][i]; 
			      
					if(!in_Q[G[nod][i]]) 
					{
					  if(cnt_Q[G[nod][i]] > N) ciclu_negativ = true;
                      else 
                      {
					    Q.push(G[nod][i]); 
						in_Q[G[nod][i]] = true; 
					    ++cnt_Q[G[nod][i]];
					  }
					}
				}
		}
	}
}

int main() 
{
	int i, x, y, c;
	in >> N >> M; 
	
	for(i = 1; i <= M; i++) 
	{
		in >> x >> y >> c; 
		G[x].push_back(y);
        C[x].push_back(c);		
	}

	solve();
	
	for(i = 2; i <= N; i++) 
		
		out << (dist[i] < INF ? dist[i] : 0) << " "; 
}