#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;
  }
};

bool viz[NMAX+5];
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();
    if ( !viz[x.a] ) {
      viz[x.a] = true;
      Sol[x.a] = x.l;
      for ( int i = 0 ; i < v[x.a].size() ; ++i ) {
        if ( !viz[v[x.a][i].b] ) {
          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;
}