#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <set>
using namespace std;
vector<bool> visited;
vector<vector<int> > adj;
vector<vector<int> > cost;
vector<int> path;
set<pair<int,int> > Q;
int count;

void dijkstra(int n)
{
	while (!Q.empty()){
		int cst,k;
		do{
			set<pair<int,int> >::iterator fe= Q.begin();
			cst = fe->first;
			k = fe->second;	
			Q.erase(fe);
		}while (visited[k] && !Q.empty());
		if (!visited[k]){
			visited[k]=true;
			path[k] = cst;
			for (int i=0;i<adj[k].size();i++)
			{
				if (!visited[adj[k][i]])
				{
					pair<int,int> t(cost[k][i]+cst,adj[k][i]);
					Q.insert(t);
				}
			}
		}
	}
}
int main()
{
	FILE *f = fopen("dijkstra.in","r");
	FILE *g = fopen("dijkstra.out","w+");
	int n,m;
	fscanf(f,"%d %d",&n,&m);
	adj.resize(n+1);
	visited.resize(n+1);
	path.resize(n+1);
	cost.resize(n+1);
	for (int i=0;i<=n;i++){
		visited[i]= false;
		path[i] = 0;
	}
	for (int i=0;i<m;i++)
	{
		int a,b,c;
		fscanf(f,"%d %d %d", &a,&b,&c);
		adj[a].push_back(b);		
		cost[a].push_back(c);
	}
	pair<int,int> r;
	r.first = 0;
	r.second = 1;
	Q.insert(r);
	dijkstra(n);
	for (int i=2;i<=n;i++)
		fprintf(g,"%d ",path[i]);
	fclose(f);
	fclose(g);
}