#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define inf 1000000000
#define NMax 50005
using namespace std;

int d[NMax],viz[NMax];
vector<pair<int,int> > vc[NMax];
priority_queue<pair<int,int>,
               vector<pair<int,int> >,
               greater<pair<int,int> > > Q;

int main ()
{
    int N,M,i,x,y,z,nod;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1; i<=M; i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        vc[x].push_back(make_pair(y,z));
    }
    for (i=2; i<=N; i++)
        d[i]=inf;
    Q.push(make_pair(0,1));
    while (!Q.empty())
    {
        nod=Q.top().second;
        viz[nod]=1;
        Q.pop();
        for (i=0; i<vc[nod].size(); i++)
            if (!viz[vc[nod][i].first] && d[vc[nod][i].first]>d[nod]+vc[nod][i].second)
            {
                d[vc[nod][i].first]=d[nod]+vc[nod][i].second;
                Q.push(make_pair(d[vc[nod][i].first],vc[nod][i].first));
            }
    }
    for (i=2; i<=N; i++)
        printf("%d ",(d[i]==inf) ? 0 : d[i]);
    return 0;
}