#include <bits/stdc++.h>
#define NMAX 50000
#define INF 1000000000

using namespace std;


struct Edge {
    int dest;
    long long cost;
    bool operator<(const Edge& other) const
    {
        return cost>other.cost;
    }
};

priority_queue<Edge> pq;
vector<pair<int,long long>> G[NMAX + 1];
long long dist[NMAX + 1];



int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int m, n, i, a, b, c;
    fin>>n>>m;
    for( i = 1; i <= n; i ++  )
      dist[i] = INF;
    for( i = 1; i <= m; i ++ ) {
      fin>>a>>b>>c;
      G[a].push_back({b,c});
    }
    pq.push({1,0});
    while( !pq.empty() ) {
      int node = pq.top().dest;
      long long cost = pq.top().cost;
      pq.pop();
      if( dist[node] == INF ) {
        dist[node] = cost;
        for( auto it : G[node] ) {
          if( dist[it.first] == INF )
            pq.push({it.first,dist[node] + it.second});
        }
      }
    }
    for( i = 2; i <= n; i ++ ) {
      if( dist[i] == INF )
        fout<<"0 ";
      else
        fout<<dist[i]<<" ";
    }
    return 0;
}