#include <stdio.h>
#include <vector>
#define inf (1<<30)
using namespace std;
//int d[200],a[200][200],n,m;
//bool viz[200];
struct graf{int nod,c;};
vector<int> d,viz;
vector<graf> a[50001];
int n,m;



void citire(){
    int x,y,c;
    graf g;
    scanf("%d %d",&n,&m);
    /*for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=inf;*/
    d.resize(n+1,0);
    viz.resize(n+1,0);

    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&c);
        //a[x][y]=c;
        g.c=c;
        g.nod=y;
        a[x].push_back(g);
    }
}

int cauta( vector<graf> g, int x){
    for(std::vector<graf>::iterator it=g.begin();it!=g.end();it++ )
        if((*it).nod==x)return (*it).c;
    return inf;
}

void dijkstra(){
    int minim,k,poz;
    for(int i=2;i<=n;i++)
        d[i]=cauta(a[1],i);
    bool ok=true;
    d[1]=0;
    viz[1]=1;
    while(ok){
        minim=inf;
        for(int i=2;i<=n;i++)
            if(d[i]<minim&&!viz[i]){
                minim=d[i];
                poz=i;
            }

        if(minim!=inf){
            viz[poz]=1;
            for(int i=2;i<=n;i++){
                k=cauta(a[poz],i);
                if(!viz[i]&&d[i]>d[poz]+k)
                    d[i]=d[poz]+k;}

        }
        else ok=false;
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    for(std::vector<int>::iterator it=d.begin()+2; it!=d.end(); ++it)printf("%d ",(*it)==inf?0:(*it));
    return 0;
}