#include <fstream>
#include <vector>
#include <queue>

const int NMAX = 50000;
using namespace std;

ifstream cin ( "dijkstra.in" );
ofstream cout ( "dijkstra.out" );

int N, M;

class Latura {
public :
  int b, length;
};

class Arc {
public :
  int a, l;
  bool operator < ( const Arc &other ) const {
    if ( l != other.l )
      return true;
    return false;
  }
};

int Sol[NMAX+5];

priority_queue <Arc> q;
vector <Latura> v[NMAX+5];

int main() {
  int a;
  Latura aux;
  Arc x, y;
  cin >> N >> M;
  for ( int i = 1 ; i <= M ; ++i ) {
    cin >> a >> aux.b >> aux.length;
    v[a].push_back ( aux );
  }
  x.a = 1;
  x.l = 0;
  q.push ( x );
  while ( !q.empty() ) {
    x = q.top();
    q.pop();
    Sol[x.a] = x.l;
    for ( int i = 0 ; i < v[x.a].size() ; ++i ) {
      y.a = v[x.a][i].b;
      y.l = x.l + v[x.a][i].length;
      q.push ( y );
    }
  }
  for ( int i = 2 ; i <= N ; ++i )
    cout << Sol[i] << ' ';
  return 0;
}