#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <ctime>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 60010;
const int maxm = 250010;

int dist[maxn];
int parent[maxn];
int inqueue[maxn];

vector<pair<int,int> > G[maxn];
queue<int> Q;

//ifstream fin("dijkstra.in");
//ofstream fout("dijkstra.out");

FILE *fin,*fout;

void getparams(char line[],int &x,int &y,int &c) {
	int l = strlen(line);
	int p = 0;
	x = 0;
	while (line[p] != ' ' && p < l) {
		x = x * 10 + line[p] - '0';
		p++;
	}
	p++;
	y = 0;
	while (line[p] != ' ' && p < l) {
		y = y * 10 + line[p] - '0';
		p++;
	}
	p++;
	c = 0;
	while (line[p] >= '0' && line[p] <= '9' && p < l) {
		c = c * 10 + line[p] - '0';
		p++;
	}
}

int main() {
	
	clock_t start = clock();
	
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	ios::sync_with_stdio(false);
	
	int n,m,x,y,c;
	
	char line[255];
	
	//fin >> n >> m;
	scanf("%d%d\n",&n,&m);
	
	for (int i=0;i<m;++i) {
		//fin >> x >> y >> c;
		//scanf("%d%d%d\n",&x,&y,&c);
		fgets(line,sizeof(line),stdin);
		getparams(line,x,y,c);
		//cerr << x << " " << y << " " << c << "\n"; 
		x--;
		y--;
		G[x].push_back(make_pair(y,c));
	}

	clock_t now = clock();
	cerr << now - start << "\n";
	
	memset(dist,-1,sizeof(dist));
	memset(inqueue,0,sizeof(inqueue));
	
	dist[0] = 0;
	Q.push(0);
	inqueue[0] = 1;
	int ops = 0;
	
	while (!Q.empty()) {
		x = Q.front();
		Q.pop();
		inqueue[x] = 0;
		for (int i=0;i<G[x].size();++i) {
			ops++;
			if (dist[G[x][i].first] == -1 || dist[G[x][i].first] > dist[x] + G[x][i].second) {
				dist[G[x][i].first] = dist[x] + G[x][i].second;
				if (inqueue[G[x][i].first] == 0) Q.push(G[x][i].first);
			}
		}
	}
	
	now = clock();
	cerr << now - start << "\n";
	
	for (int i=1;i<n;++i) 
		//fout << (dist[i] == -1 ? 0 : dist[i]) << " ";
		printf("%d ",(dist[i] == -1 ? 0 : dist[i]));
		
	printf("\n");
	/*
	fin.close();
	fout.close();
	*/
	
	fclose(stdin);
	fclose(stdout);
	
	now = clock();
	cerr << now - start << "\n";
	
	return 0;
}