#include <bits/stdc++.h>
using namespace std;

const int nmax = 50005;
int n, m, dist[nmax];
vector< pair<int,int> > g[nmax];
bool marked[nmax];

void apply_dijkstra()
{
    int i, nod;
    pair<int, int> p;
	set< pair<int,int> > s;
	s.insert(make_pair(0,1));
	dist[1] = 0;
	marked[1] = 1;
	while(!s.empty())
	{
        p=*s.begin();
        nod=p.second;
		s.erase(p);
		marked[nod] = 2;
		for(i=0; i<g[nod].size(); i++)
			if(marked[g[nod][i].second]==0)
			{
				s.insert(make_pair(dist[nod]+g[nod][i].first, g[nod][i].second));
				marked[g[nod][i].second] = 1;
				dist[g[nod][i].second] = dist[nod]+g[nod][i].first;
			}
			else if(marked[g[nod][i].second]==1 && dist[g[nod][i].second] > dist[nod]+g[nod][i].first)
			{
				s.erase(make_pair(dist[g[nod][i].second],g[nod][i].second));
				s.insert(make_pair(dist[nod]+g[nod][i].first,g[nod][i].second));
				dist[g[nod][i].second] = dist[nod]+g[nod][i].first;
			}
	}
	for(i=2; i<=n; i++)
		printf("%d ",dist[i]);
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int x, y, c;
	scanf("%d %d",&n, &m);
	for(int i=0; i<m; i++)
	{
		scanf("%d %d %d",&x, &y, &c);
		g[x].push_back(make_pair(c, y));
	}
	apply_dijkstra();
	fclose(stdin);
	fclose(stdout);
	return 0;
}