#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

vector<vector<pair<int,int>>> v;
int n,m,x,y,c;
int viz[50001];
int max1 = 2000001;

int d[50001];

struct cmp
{
	bool operator()(pair<int,int> x, pair<int, int> y)
	{
		return x.second > y.second;
	}
};

priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> q;

void dijkstra(int x)
{
	for (int i = 1; i <= n; i++)
	{
		d[i]=max1;
	}
	d[x] = 0;
	q.push({ x,0 });
	while (!q.empty())
	{
		x=q.top().first;
		q.pop();
		if (viz[x] == 1)
		{
			continue;
		}
		viz[x] = 1;
		for (auto i = 0u; i < v[x].size(); i++)
		{
			y=v[x][i].first;
			c=v[x][i].second;
			if (d[y] > d[x] + c)
			{
				d[y] = d[x] + c;
				q.push({ y,d[y] });
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	v=vector<vector<pair<int,int>>>(n+1);
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y >> c;
		v[x].push_back({ y,c });
	}
	dijkstra(1);
	for (int i = 2; i <= n; i++)
	{
		if (d[i] == max1)
		{
			cout << 0 <<" ";
		}
		else
		{
			cout << d[i] << " ";
		}
	}
    return 0;
}