#include <bits/stdc++.h>

using namespace std;


ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct node{
		int val,dist;
	
}heap[400000];
int N;
vector <node> V[100001];
int link[400001],n,m;
int drum[100001];
int leftson(int x) {
	return 2*x;
}
int rightson(int x){
	return 2*x+1;
}
int father(int x){
	return x/2;
}



void go_up(int k){
	int parent;
	if (k!=0){
		parent=father(k);
		if (heap[parent].dist>heap[k].dist){
			swap(heap[parent],heap[k]);
			swap(link[heap[parent].val],link[heap[k].val]);
			go_up(parent);
			
		}
	}
	else return ;
	
}

void insert(node val){
	heap[++N]=val;
	link[heap[N].val]=N;
	go_up(N);
	
}

node getmin(){
	return heap[1];
}

void go_down(int k){
	int minindex;
	if (rightson(k)>=N){
		if (leftson(k)>=N) return ;
		else minindex=leftson(k);
		
		
	} else {
		if (heap[leftson(k)].dist<=heap[rightson(k)].dist)
					minindex=leftson(k);
		else 
					minindex=rightson(k);
	}
	if (heap[k].dist>heap[minindex].dist){
		swap(heap[k],heap[minindex]);
		swap(link[heap[k].val],link[heap[minindex].val]);
		go_down(minindex);
	}
	
	
}

void pop(){
	link[heap[1].val]=-1;
	link[heap[N].val]=1;
	heap[1]=heap[N];
	N--;
	go_down(1);
	
}

void update(int poz,int newv){
	heap[poz].dist=newv;
	go_up(poz);
}

void readit(){
	fin >>n>>m;
	for (int i=1;i<=m;i++){
		int a,b,c;
		node x;
		fin >>a>>b>>c;
		x.val=b;
		x.dist=c;
		V[a].push_back(x);
	}
	
}

void dijkstra(){
	node x;
	x.val=1;
	x.dist=0;
	insert(x);
	x.dist=1e9;
	for (int i=2;i<=n;i++) {
		x.val=i;
		insert(x);
	}
	
	
	while (N){
			node source=getmin();
			pop();
			drum[source.val]=source.dist;
			for (int i=0;i<V[source.val].size();i++){
				if (V[source.val][i].dist+drum[source.val]<heap[link[V[source.val][i].val]].dist)
				update(link[V[source.val][i].val],V[source.val][i].dist+drum[source.val]);
				
			}
		
		
	}
	for (int i=2;i<=n;i++) fout <<max(drum[i],-1)<<" ";
}
int main(){
	readit();
	dijkstra();
	
	return 0;
	
}