#include <bits/stdc++.h>
#define inf 10000000
#define NMAX 100001
using namespace std;

int n,m,dist[NMAX];
vector < vector<pair <int,int> > > la;
vector < pair <int ,int > >::iterator it;

FILE *fin = fopen("dijkstra.in","r");
FILE *fout = fopen("dijkstra.out","w");

void citire()
{
    int x,y,z;
    fscanf(fin,"%d %d ",&n,&m);
    la.resize(n+1);
    for(int i=1;i<=m;++i)
        {
            fscanf(fin,"%d %d %d",&x,&y,&z);
            la[x].push_back(make_pair(y,z));
        }
}

void dijsktra()
{
    for(int i=1;i<=n;++i)dist[i] = inf;
    dist[1]=0;
    priority_queue < pair<int,int> , vector<pair<int,int> > , greater <pair<int,int > > > q;
    q.push(make_pair(0,1));
    while(q.empty() == false)
    {
        int v = q.top().second;
        q.pop();
        for(it = la[v].begin();it!=la[v].end();++it)
        {
            int vecin = it->first;
            int dvecin = it->second;
            if(dist[vecin] > dist[v] + dvecin)
            {
                dist[vecin] = dist[v] + dvecin;
                q.push(make_pair(dist[vecin],vecin));
            }
        }
    }
    for(int i=2;i<=n;++i)
        if(dist[i] == inf)fprintf(fout,"0 ");
    else fprintf(fout,"%d ",dist[i]);
}

int main()
{
    citire();
    dijsktra();
}