#include <fstream.h>
#define maxn 50001
const int inf = 1 << 30;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m, d[maxn], q[maxn];
struct graf {int nod, cost;
             graf *urm;
			};
graf *a[maxn];
void add(int adresa, int nodul, int cost)
{graf *q = new graf;
 q->nod = nodul;
 q->cost = cost;
 q->urm = a[adresa];
 a[adresa] = q;
}
void citire()
{f>>n>>m;
 int x, y, z;
 for (int i = 1; i <= m; ++i){f>>x>>y>>z;
                              add(x, y, z);
                             }
}
void dijkstra()
{for (int i = 2; i <= n; i++) d[i] = inf;
 int min, pmin = 0;
 for (int i = 1; i <= n;i++)
      {min = inf;
	   for (int j = 1; j <= n; ++j ) if ( d[j] < min && !q[j] ) min = d[j], pmin = j;
       q[pmin] = 1;
	   graf *t = a[pmin];
       while ( t )
           {if ( d[ t->nod ] > d[pmin] + t->cost ) d[ t->nod ] = d[pmin] + t->cost;
            t = t->urm;
           }
      }
}

int main()
{citire();
 dijkstra();
 for ( int i = 2; i <= n; ++i )
        g<<d[i]<<" ";
 g<<"\n";;
 g.close();
 return 0;
}