#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,k,a[5000][5000],v[500],d[500],t[500],inf=2000000000,mi;

void citire() {
    int x,y,z;
    f>>n>>m;
    for(int i=1; i<=m; i++) {
        f>>x>>y>>z;
        a[x][y]=z;
        a[y][x]=z;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) if(!a[i][j]) a[i][j]=inf;
}

void dijkstra(int x) {
    int ok=1,k;
    for(int i=1; i<=n; i++) {
        d[i]=a[x][i];
        if(d[i]<inf && d[i]>0) t[i]=x;
    }
    v[x]=1;
    t[x]=0;
    while(ok) {
        mi=inf;
        for(int i=1; i<=n; i++)
            if(v[i]==0 && d[i]<mi) {
                mi=d[i];
                k=i;
            }
        if(mi==inf) ok=0;
        else {
            v[k]=1;
            for(int i=1; i<=n; i++)
                if(!v[i] && d[i]>d[k]+a[k][i]) {
                    d[i]=d[k]+a[k][i];
                    t[i]=k;
                }
        }
    }
}

void afisare(int x) {
    /*for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++)
            g<<setw(5)<<a[i][j];
        g<<'\n';
    }*/
    if(x) {
        afisare(t[x]);
        g<<x<<" ";
    }
}

int main() {
    citire();
    dijkstra(1);
    for(int i=2; i<=n; i++) {
        //afisare(i);
        g<<d[i]<<" ";
    }
    return 0;
}