#include <fstream>
#include <vector>
#include <queue>
#define mp make_pair
#define pb push_back

using namespace std;

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

const int N=51000;

vector < pair <int,int> > edge[N];
priority_queue < pair <int,int> > heap; // bag in heap distanta tentativa si nodul 

bool visited[N];
int dist[N];

int n,m;

void read(){
	int i,x,y,c;
	in>>n>>m;
	for(i=1;i<=m;++i){
		in>>x>>y>>c;
		edge[x].pb(mp(y,-c));
	}	
}

void solve(){
	int i,j,vis=1,x;
	heap.push(mp(0,1));
	while(heap.empty()==false){
		x=heap.top().second;		
		if(visited[x]==1){
			heap.pop();
			continue;
		}
		dist[x]=heap.top().first;
		visited[x]=1;
		vis++;
		heap.pop();
		for(i=0;i<edge[x].size();++i){
			if(dist[x]+edge[x][i].second<dist[edge[x][i].first]){
				heap.push(mp(dist[x]+edge[x][i].second,edge[x][i].first));
			}
		}
	}
}

void print(){
	int i;
	for(i=2;i<=n;++i){
		out<<-dist[i]<<" ";
	}
}

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