/// 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 (index != pminim) {
        pminim = index;
        int minim = dist[H[index]];
        if (index*2 <= heapSize && minim > dist[H[index*2]]) {
            minim = dist[H[index*2]];
            pminim = index*2;
        }
        if (index*2+1 <= heapSize && minim > dist[H[index*2+1]]) {
            minim = dist[H[index*2+1]];
            pminim = index*2+1;
        }

        swapH(pminim, index);
        index = pminim;
    }
}
*/

void heapDown(int what)
{
    int w;
    while ( what <= heapSize )
    {
        w = what;
        if ( (what<<1) <= heapSize )
        {
            w = what << 1;
            if ( w + 1 <= heapSize )
                if ( dist[ H[w + 1] ] < dist[ H[w] ] )
                    ++w;
        }
        else
            return;

        if ( dist[ H[what] ] > dist[ H[w] ] )
        {
            swapH(what, w);

            what = w;
        }
        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;
}