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

#define NMax 50005
const int inf = 1 << 30;

using namespace std;

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

struct graf {

    int nod;
    int costToGetHere;
    graf *previousNode;
};

int n,m;
int d[NMax], visited[NMax];
graf *a[NMax];

void dijkstra() {

    int minim, pminim=0;
    for (int i=2;i<=n;i++)
        d[i] = inf, visited[i] = 0;

    for (int i=1;i<=n;i++) {
        minim = inf;
        for (int j=1;j<=n;j++) {
            if (d[j] < minim && !visited[j]) {
                minim = d[j];
                pminim = j;
            }
        }

        visited[pminim] = 1;

        graf *t = a[pminim];
        while (t) {
            if (d[t->nod] > d[pminim] + t->costToGetHere) {
                d[t->nod] = d[pminim] + t->costToGetHere;
            }
            t = t->previousNode;
        }
    }
}

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

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

int main() {

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

    dijkstra();

    for (int i=2;i<n;i++) {
        g<<d[i]<<' ';
    } g<<d[n]<<'\n';

    f.close();

    return 0;
}