/// Craciun Catalin
///  Dijkstra
#include <iostream>
#include <fstream>

#define NMax 200005
#define inf 1<<30

struct graf {

    int nod, cost;
    graf *next;
    graf() {
        nod = cost = 0;
        next = NULL;
    }
};

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m;
graf *a[NMax];
int dist[NMax];
int poz[NMax];
int H[NMax];
int heapSize = 0;

void swapH(int i, int j) {

    poz[H[j]] = i;
    poz[H[i]] = j;

    int aux = H[i];
    H[i] = H[j];
    H[j] = aux;
}

void output() {

    for (int i=2;i<n;i++) {
        if (dist[i] == inf)
            g<<0<<' ';
        else
            g<<dist[i]<<' ';
    }
    if (dist[n] == inf)
        g<<0<<' ';
    else
        g<<dist[n]<<' ';

    g<<'\n';
}

void heapUp(int index) {
    while (index > 1) {
        if (dist[H[index]] < dist[H[index/2]])
            swapH(index, index/2);
        else
            break;

        index /= 2;
    }
}

void heapDown(int index) {
    int pminim = -1;
    while (1) {
        if (2*index <= heapSize) {
            int value = dist[H[2*index]];
            pminim = 2*index;
            if (2*index+1 <= heapSize) {
                if (value > dist[H[2*index+1]]) {
                    value = dist[H[2*index+1]];
                    pminim = 2*index+1;
                }
            }

            if (value < dist[H[index]]) {
                swapH(index, pminim);
                index = pminim;
            } else
                return;
        } else
            return;
    }
}

void dijkstra() {

    for (int i=2;i<=n;i++) {
        dist[i] = inf;
        poz[i] = -1;
    }

    H[++heapSize] = 1;
    poz[1] = 1;
    dist[1] = 0;

    while (heapSize > 0) {
        int nod = H[1];
        swapH(1, heapSize);
        poz[H[1]] = 1;
        heapSize--;

        heapDown(1);

        graf *q = a[nod];
        while ( q ) {
            if (dist[q->nod] > q->cost + dist[nod]) {
                dist[q->nod] = q->cost + dist[nod];
                if (poz[q->nod] == -1) {
                    heapSize++;
                    H[heapSize] = q->nod;
                    poz[q->nod] = heapSize;
                    heapUp(heapSize);
                } else {
                    heapUp(poz[q->nod]);
                }
            }

            q = q->next;
        }
    }
}

void add(int where, int what, int cost) {

    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}

void read() {

    f>>n>>m;
    for (int i=1;i<=m;i++) {
        int x, y, c;
        f>>x>>y>>c;
        add(x,y,c);
    }
}

int main() {

    read();
    dijkstra();
    output();

    f.close(); g.close();
    return 0;
}