#include <fstream>
#include <set>
#include <utility>
#include <queue>
#include <bitset>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int inf = 0x3f3f3f3f;
int N, M;
int cost[50005];
set<pair<int, int> > G[50005];
bitset<50005> witness;
int main()
{
int i, A, B, C, node;
set<pair<int, int> >::iterator it;
queue<int> Q;
cin >> N >> M;
fill_n(cost + 2, N, inf);
for (i = 0; i < M; ++i)
{
cin >> A >> B >> C;
G[A].insert(make_pair(B, C));
}
Q.push(1);
witness[1] = true;
while(!Q.empty())
{
node = Q.front();
witness[node] = false;
for (it = G[node].begin(); it != G[node].end(); ++it)
{
if (cost[node] + it->second < cost[it->first])
{
cost[it->first] = cost[node] + it->second;
if (witness[it->first] == false)
{
Q.push(it->first);
witness[it->first] = true;
}
}
}
Q.pop();
}
for (i = 2; i <= N; ++i)
{
if (cost[i] == inf)
cout << "0 ";
else cout << cost[i] << ' ';
}
cout << '\n';
cout.close();
return 0;
}