#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int N= 50005;
const int oo = 1 << 30;

vector <pair <int,int> > g[N];
int n,m,c[N];

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

int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
        c[i] = oo;
    for(int x,y,cost, i=0; i<m ; ++i)
    {
        fin>> x >> y >> cost;
        g[x].push_back(make_pair (y,cost));
    }
    H.push (make_pair (0,1)); /// (c[i],i)
    c[1] = 0;

    while (H.size())
    {
        int cost = H.top().first;
        int x = H.top().second;
        H.pop();
        if(cost > c[x])
           continue;
        for(int i=0; i< g[x].size(); i++)
         {
             if( c[g[x][i].first] > cost + g[x][i].second )
              {
                c[g[x][i].first] = cost + g[x][i].second ;
                H.push (make_pair (cost + g[x][i].second, g[x][i].first) ) ;
              }
         }
    }
    for(int i=2;i<=n;i++)
    if(c[i] == oo)
      fout <<"0 ";
    else
      fout<< c[i]<<" ";
    return 0;
}