#include <iostream>
#include <queue>
using namespace std;

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define INF 0x3f3f3f3f
#define MAXN 50001

int n, m;
int D[MAXN], T[MAXN];

struct item { int nod, cost; item *r; } *L[MAXN];

struct Comp {
    bool operator()(const int &a, const int &b) {
        return D[a] > D[b];
    }
};

priority_queue<int, vector<int>, Comp> C;

void dijkstra(int s)
{
    int crt;
    memset(D, INF, sizeof(D));
    D[s] = T[0] = 0;
    C.push(s);
    while (!C.empty()) {
        crt = C.top(); C.pop();
        for (item *p = L[crt]; p; p = p->r) {
            if (D[crt] + p->cost < D[p->nod]) {
                D[p->nod] = D[crt] + p->cost;
                T[p->nod] = crt;
                C.push(p->nod);
            }
        }
    }
}

void citeste()
{
    int x, y, c;
    freopen(FIN, "r", stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d", &n, &m);
    while (m--) {
        scanf("%d %d %d", &x, &y, &c);
        item *p = new item;
        *p = (item) { y, c, L[x] };
        L[x] = p;
    }
}

int main()
{
    citeste();
    dijkstra(1);
    for (int i=2; i<=n; ++i)
        printf("%s%d", i==2?"":" ", D[i]);
    printf("\n");
    return 0;
}