#include <bits/stdc++.h>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int nmax=50005;
const int inf=1<<30;

vector <pair <int,int> > a[nmax];
int n,m,cost[nmax],x,y,c,costac,nodac,vecini;

priority_queue <pair <int , int>  , vector <pair <int , int> > , greater <pair <int , int> > > H;

int main()
{
    int i;
    f>>n>>m;

    for (i=1;i<=n;i++)
     cost[i]=inf;

    for (i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(y,c));
    }

    cost[1]=0;
    H.push(make_pair(0,1)); /// cost,nod

    while (H.size())
    {
        costac=H.top().first;
        nodac =H.top().second;
        H.pop();

        if (costac>cost[nodac])
         continue;

        vecini=a[nodac].size();

        for (i=0;i<vecini;i++)
        {
             if (cost[a[nodac][i].first]>costac + a[nodac][i].second)
             {
                 cost[a[nodac][i].first]=costac + a[nodac][i].second;
                 H.push(make_pair(costac + a[nodac][i].second,a[nodac][i].first));
             }
        }
    }

    for (i=2;i<=n;i++)
     if (cost[i]==inf)
      g<<"0 ";
     else g<<cost[i]<<" ";

    return 0;
}