#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int mx=60000;
const long long inf=2e18;

struct edge{
	int dest,cost;
};

struct node{
	int index;
	long long cost;
};

struct compare{
	bool operator()(const node&a,const node&b){
		return a.cost>b.cost;
	}
};

vector<edge> g[mx];
long long dist[mx];
int n,m;

void read(){
	fin>>n>>m;
	int a,b,c;
	for(int i=0;i<m;i++){
		fin>>a>>b>>c;
		g[a].push_back({b,c});
	}
}

void solve(){
	for(int i=1;i<=n;i++)
		dist[i]=inf;

	priority_queue<node,vector<node>,compare> q;	
	dist[1]=0;
	q.push({1,0});

	while(!q.empty()){
		node top=q.top();
		q.pop();
		
		if(top.cost>dist[top.index])
			continue;

		for(edge&e:g[top.index]){
			long long newcost=top.cost+e.cost;
			if(dist[e.dest]>newcost){
				dist[e.dest]=newcost;		
				q.push({e.dest,newcost});
			}
		}
	}
	for(int i=2;i<=n;i++){
		fout<<((dist[i]==inf)? 0:dist[i])<<" ";
	}
}

int main(){
	read();
	solve();
	return 0;
}