#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>
#define mp make_pair
#define pb push_back
#define TR(C, i)\
for(i = C.begin(); i < C.end(); i++)
#define ver first
#define dist second
#include <string.h>
using namespace std;
const int nmax = 50100;
const int oo = 0x6f6f6f6f;
int N, M;
int D[nmax];
vector< pair < int, int > > G[nmax];
void read()
{
freopen ("dijkstra.in", "r", stdin);
freopen ("dijkstra.out", "w", stdout);
scanf("%d %d", &N, &M);
int i, a, c, b;
for(i = 1; i <= M; i++)
{
scanf("%d %d %d", &a, &b, &c);
G[a].pb(mp(b, c));
}
}
struct cmp
{
bool operator()(const int &a, const int &b)const{
return D[a] > D[b];
}
};
priority_queue <int, vector<int>, cmp> Q;
void Dijkstra()
{
memset(D, oo, sizeof(D));
vector< pair < int, int > >::iterator it;
int nod, i;
D[1] = 0;
Q.push(1);
while(!Q.empty())
{
nod = Q.top();
Q.pop();
TR(G[nod], it)
if(D[nod] + it->dist < D[it->ver])
{
D[it->ver] = D[nod] + it->dist;
Q.push(it->ver);
}
}
for(i = 2; i <= N; i++)
if(D[i] == oo) printf("0 ");
else printf("%d ", D[i]);
}
int main()
{
read();
Dijkstra();
return 0;
}