#include <iostream>
#include <fstream>
#include <climits>
#define NMAX 16358
#define INF INT_MAX
#define INFILE "dijkstra.in"
#define OUTFILE "dijkstra.out"
#define start 1

using namespace std;
typedef long ints;
int n;
int m;
ifstream in(INFILE);
ofstream out(OUTFILE);
ints C[NMAX][NMAX];
ints parent[NMAX];
ints d[NMAX];
bool M[NMAX];
void Initializare(){
    in>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            C[i][j]=C[j][i]=INF;
    }
    for(int i=1;i<=m;i++){
        int x,y;
        ints c;
        in>>x>>y>>c;
        C[x][y]=c;
    }
    for(int i=1;i<=n;i++){
        d[i]=INF;
        parent[i]=start;
    }
    d[start]=0;
    parent[start]=0;

}

int MinVf(){
    ints Min=INF;
    int i_min;
    for(int i=1;i<=n;i++){
        if(d[i]<Min&&M[i]==false){
            Min=d[i];
            i_min=i;
        }
    }
    cout<<Min<<endl;
    return i_min;
}

int Dijkstra(){
    for(int i=1;i<=n-1;i++){
        int u=MinVf();
        M[u]=true;
        for(int v=1;v<=n;v++){
            if(M[v]==false&&d[v]>d[u]+C[u][v]){
                d[v]=d[u]+C[u][v];
                parent[v]=u;
            }
        }
    }
}

void Afisare(){
    for(int i=1;i<=n;i++)
        out<<d[i]<<" ";
}

int main()
{
    Initializare();
    Dijkstra();
    Afisare();
    return 0;
}