// 再来一手精髓的Dijkstra

 // 复杂度O( E*log(V) )

 #include <cstdio>

 #include <iostream>

 #include <vector>

 #include <queue>

 using namespace std;

 const int max_N = +;

 const int max_E = +;

 const int INF = 1e9;

 int N,E;

 int d[max_N];

 // 来自何方，已经不重要了。

 // 实际上是在邻接表实现的过程中，行号即为来自的顶点

 struct edge

 {

     int to,cost;

 };

 // P.first代表距离，P.second代表顶点编号

 typedef pair<int,int> P;

 vector<edge> G[max_N];

 // 这一个算法下来，我们在数组d中得到了从s点到其余所有顶点的最短路程

 void dijkstra(int s)

 {

     // 建立最堆，来维护最小距离，可以降低一层复杂度

     priority_queue< P,vector<P>,greater<P> > que;

     fill(d,d+N,INF);

     d[s]=;

     que.push(P(,s));

     while(!que.empty())

     {

         // 取出一个顶点，看是否是Dijstra算法中，已经确定的最小顶点

         P p=que.top();

         que.pop();

         int v=p.second;

         // 让我们来看看这一步

         // 首先，每次取出堆中的最小元素

         // 然后去检索这个堆顶元素的标号所对应的距离

         // 咦，你会发现堆顶这个距离，竟然比取出的最小元素还要小

         // 惊讶？难道出错了？没有，考虑Dijkstra算法的流程，这个顶点肯定是之前已经确定过的最小顶点了，不需要考虑

         // 之前的实现是多加了一个flag数组来标记，这里可以省去这部分内存，直接用这个条件来判断

         if(d[v]<p.first)

         {

             continue;

         }

         for(int i=;i<G[v].size();++i)

         {

             edge e=G[v][i];

             if(d[e.to] > d[v] + e.cost)

             {

                 d[e.to]=d[v]+e.cost;

                 // 数组中维护此次被更新的节点即可，其余节点不需要维护

                 que.push(P(d[e.to],e.to));

             }

         }

     }

 }

 int main()

 {

     int a,b,c;

     scanf("%d %d",&N,&E);

     for(int i=;i<E;++i)

     {

         scanf("%d %d %d",&a,&b,&c);

         edge e;

         e.to=b;

         e.cost=c;

         G[a].push_back(e);

         // 无向图

         e.to=a;

         e.cost=c;

         G[b].push_back(e);

     }

     dijkstra();

     for(int i=;i<N;++i)

     {

         printf("%d ",d[i]);

     }

     return ;

 }

 /*

 7 10

 0 1 2

 0 2 5

 1 2 4

 1 3 6

 1 4 10

 2 3 2

 3 5 1

 4 5 3

 4 6 5

 5 6 9

 */