#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct per{
    int nod, cost;
    bool operator<(const per& other) const {
        return (*this).cost > other.cost;
    }
};

int n, i, cost[50005], m, s, f, x, y, d;
vector<per> v[50005];
priority_queue<per> q;

void dijkstra( int s ){
     for ( i = 1; i <= n; i++ ) cost[i] = 1e9;
     cost[s] = 0;
     q.push({s, 0});
     while ( !q.empty() ){
             per x = q.top();
             q.pop();
             for ( auto el:v[x.nod] ){
                   if ( cost[el.nod] > x.cost + el.cost ){
                        cost[el.nod] = x.cost + el.cost;
                        q.push({el.nod, x.cost + el.cost});
                   }
             }
     }
}

int main()
{
    fin >> n >> m;
    for ( i = 1; i <= m; i++ ){
          fin >> x >> y >> d;
          v[x].push_back({y, d});
    }
    dijkstra(1);
    for ( i = 2; i <= n; i++ ){
          if ( cost[i] == 1e9 ) fout << "0" << " ";
          else fout << cost[i] << " ";
    }
}