#include <fstream>
#include <vector>
#include <limits.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,minim,p;
int D[50001];
bool viz[50001];

vector <int> L[50001],C[50001];

int main(void){
    register int i,j,x,y,z;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>z;
        L[x].push_back(y);
        C[x].push_back(z);
    }
    for(i=2;i<=n;i++)
        D[i]=INT_MAX;

    D[0]=n;
    while(D[0]){
        minim=INT_MAX;
        for(i=1;i<=n;i++){
            if(!viz[i] && D[i]<minim){
                minim=D[i];
                p=i;
            }
        }
        viz[p]=true;
        D[0]--;
        for(i=0;i<L[p].size();i++){
            if(D[L[p][i]]>D[p]+C[p][i]){
                D[L[p][i]]=D[p]+C[p][i];
            }
        }
    }

    for(i=2;i<=n;i++){
        if(D[i]==INT_MAX){
            g<<"0 ";
        }
        else{
            g<<D[i]<<" ";
        }
    }
    f.close();
    g.close();
    return 0;
}