#include <stdio.h>

const int maxn = 100001;    // nr maxim de noduri
const int inf = 2e9;    // infinit

FILE *fin = fopen( "dijkstra.in", "r" );
FILE *fout = fopen( "dijkstra.out","w" );

struct nod {
  int nr_nod, cost;
  nod *next;
};

int n, m, p;
nod *L[maxn];
int d[maxn];   // costurile de la start la toate nodurile
int s[maxn];
char viz[maxn];

int heap[maxn];
int hs = 0;
void push(int x) {
    heap[hs] = x;
    int i = hs++;
    while (i > 0 && d[heap[i]] < d[heap[(i - 1) / 2]]) {
        int aux = heap[i];
        heap[i] = heap[(i - 1) / 2];
        heap[(i - 1) / 2] = aux;
        i = (i - 1) / 2;
    }
}

int pop() {
    int aux = heap[hs - 1];
    heap[hs - 1] = heap[0];
    heap[0] = aux;
    hs--;
    int i = 0;
    while (i * 2 + 1 < hs && d[heap[i]] > d[heap[i * 2 + 1]] || i * 2 + 2 < hs && d[heap[i]] > d[heap[i * 2 + 2]]) {
        int j;
        if (i * 2 + 2 == hs || d[heap[i * 2 + 1]] < d[heap[i * 2 + 2]]) {
            j = i * 2 + 1;
        } else {
            j = i * 2 + 2;
        }
        aux = heap[i];
        heap[i] = heap[j];
        heap[j] = aux;
        i = j;
    }
    return heap[hs];
}

// adauga la lista lui x nodul cu numarul y
void add( int x, int y, int cost ) {
  nod *c = new nod;
  c->nr_nod = y;
  c->cost = cost;
  c->next = L[x];  // ne legam de primul nod al listei lui x
  L[x] = c;
//  c = new nod;
//  c->nr_nod = x;
//  c->cost = cost;
//  c->next = L[y];  // ne legam de primul nod al listei lui y
//  L[y] = c;
}

void read() {
  fscanf(fin, "%d %d", &n, &m );
  p = 1;
  int x, y, cost;
  for ( int i = 1; i <= m; i++ ) {
    fscanf(fin, "%d %d %d", &x, &y, &cost);  //citim arcul si costul asociat
    add(x, y, cost);
  }
}

void dijkstra( int start ) {
  // initializam toate drumurile de la start la fiecare nod
  // dist de la start la el insusi e 0
  for ( int i = 1; i <= n; i++ )
    d[i] = inf;
  d[start] = 0;

  push(start);

  int min, pmin = 0;    // costul minim si nodul cu costul minim pana la start
  while ( hs ) {
    // determin nodul cel mai apropiat de nodul de start
    pmin = pop();
    min = d[pmin];

    if ( s[pmin] )
        continue;

    // parcurgem lista vecinilor nodului selectat pmin
    // pentru a vedea daca prin acest nod se ajunge mai repede la vecinii sai, pornind din start
    s[pmin] = 1;         // marcam ca si selectat nodul intermediar
    nod *c = L[pmin];
    while ( c ) {
      if ( !s[ c->nr_nod ] && d[ c->nr_nod ] > d[pmin] + c->cost ) { // dc costul deja memorat al nodului nr_nod e mai mare decat costul prin nodul intermediar pmin
        d[ c->nr_nod ] = d[pmin] + c->cost;       // actualizam costul in vectorul de costuri d
        push(c->nr_nod);
      }
      c = c->next;
    }
  }
}

int main() {

  read();             // citim muchiile si costurile acestora, construind listele de adiagenta
  dijkstra( p );      // calculam distantele de la nodul start la toate celelalte
  for ( int i = 2; i <= n; i++ )    // afisam dinstantele de la nodul start la fiecare nod
    fprintf(fout, "%d ", d[i] == inf ? 0 : d[i]);
  fprintf(fout, "\n");

  return 0;
}