#include <bits/stdc++.h>
#define DMAX 50007
#define inf 1000000000
// Defines for debug functions
#define dbg(x) cout << "Debugger -> " << #x << " = " << x << endl;
#define dbgs(s) cout << "Debugger " << #s << ":\n";\
for(auto i : s) \
	cout << "> " << i << ' ';\
cout << "End of " << #s << endl
// End of debug functions defines

using namespace std;

//9:03

int d[DMAX];
int n, m, a, x, y;
vector <pair<int, int> > v[DMAX];

class cmp
{
public:
	bool operator()(int a, int b)
	{
		return d[a] < d[b];
	}
};

void dijkstra(int nod)
{
	for(int i=0;i<DMAX;i++)
		d[i] = inf;
	set <int, cmp> s;

	d[nod] = 0;
	s.insert(nod);

	while(!s.empty())
	{
		int p = *s.begin();
		s.erase(p);
		for(int i=0;i<v[p].size();i++)
		{
			pair<int, int> f = v[p][i];

			if(d[p] + f.second < d[f.first])
			{
				if(s.find(f.first) != s.end())
					s.erase(f.first);
				d[f.first] = f.second + d[p];
				s.insert(f.first);
			}
		}
	}
}

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

int main()
{
	ios_base::sync_with_stdio(false);

	fin >> n >> m;
	for(int i=0; i<m; i++)
	{
		fin >> x >> y >> a;
		v[x].push_back({y, a});
	}
	dijkstra(1);

	for(int i=2;i<=n;i++)
	{
		if(d[i] == inf) d[i] = 0;
		fout << d[i] << " \n"[i==n];
	}

	return 0;
}