//Infoarena. Arhiva Educationala. Floyd-Warshall/Roy-Floyd.
#include<iostream>
#include<fstream>
using namespace std;

void roy_floyd(int[][50003],int);


int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    int N,M,P[50003][50003];
    cin>>N>>M;

    int x,y,aux;
    for(int i=1;i<=M;i++){
        cin>>x>>y>>aux;
        P[x][y]=aux;
    }

    roy_floyd(P,N);  //Generam Matricea Distantelor Minime
    for(inti=2;i<=N;i++) cout<<P[1][i]<<" ";

}

void roy_floyd(int P[103][103],int N){
    int dist;
    for(int k=1;k<=N;k++)
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++){
                if(i==j) continue;
                else if(P[i][k]&&P[k][j]){
                    dist=P[i][k]+P[k][j];
                    if(P[i][j]==0 || P[i][j]>dist) P[i][j]=dist;
                }
            }
}

void read(int P[103][103],int N){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++){
            cin>>P[i][j];
        }
}