#include <bits/stdc++.h>

using namespace std;

FILE*h2=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");

#define INF 2147483647
#define MAX 100000
#define f first
#define s second
#define mp make_pair
#define ll
int n,m;

vector<pair<int,int> >v[MAX];
priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > >h;
int d[MAX],w[MAX];

int main()
{
    int i,a,b,c,nod;
    fscanf(h2,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf(h2,"%d%d%d",&a,&b,&c);
        v[a].push_back(mp(c,b));
    }
    h.push(mp(0,1));
    d[1]=0;
    for (i=2;i<=n;i++) d[i]=INF;
    while (!h.empty()){
        nod=h.top().s;
        h.pop();
        if (!w[nod]){for (i=0;i<v[nod].size();i++)
        if (d[nod]+v[nod][i].f<d[v[nod][i].s]){
            d[v[nod][i].s]=d[nod]+v[nod][i].f;
            h.push(mp(d[v[nod][i].s],v[nod][i].s));

        }
        w[nod]=1;
        }
    }
    for (i=2;i<=n;i++) {if (d[i]==INF) d[i]=0;fprintf(g,"%d ",d[i]);}
    fclose(h2);
    fclose(g);
    return 0;
}