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

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

void apply_dijkstra()
{
    int i, nod;
    pair<int, int> p;
	set< pair<int,int> > s;
	s.insert(make_pair(1, 0));
	dist[1] = 0;
	viz[1] = 1;
	while(!s.empty())
	{
        p=*s.begin();
        nod=p.first;
		s.erase(p);
		viz[nod]=1;
		for(i=0; i<g[nod].size(); i++)
			if(viz[g[nod][i].first]==0)
			{
			    viz[g[nod][i].first]=1;
				dist[g[nod][i].first] = dist[nod]+g[nod][i].second;
				s.insert(make_pair(g[nod][i].first, dist[nod]+g[nod][i].second));
			}
			else if(viz[g[nod][i].first]==1 && dist[g[nod][i].first] > dist[nod]+g[nod][i].second)
			{
				s.erase(make_pair(g[nod][i].first, dist[g[nod][i].first]));
				s.insert(make_pair(g[nod][i].first, dist[nod]+g[nod][i].second));
				dist[g[nod][i].first] = dist[nod]+g[nod][i].second;
			}
	}
	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(y, c));
	}
	apply_dijkstra();
	fclose(stdin);
	fclose(stdout);
	return 0;
}