#include<fstream>
#include<vector>
using namespace std;

ifstream u ("dijkstra.in");
ofstream w ("dijkstra.out");

#define NMAX 50001
#define INF (1<<30)
int nrnodes, nrarcs;
int dist[NMAX];

struct muchie
{int target, cost;
};
vector<muchie> G[NMAX];

void Read()
{int i, x, y, c;
 muchie aux;

 u>>nrnodes>>nrarcs;
 for(i=1; i<=nrarcs; i++)
    {u>>x>>y>>c;
     aux.target=y;
     aux.cost=c;
     G[x].push_back(aux);
    }
}

struct hnod
{int key, val;
 bool operator<(hnod A)
    {return val<A.val;
    }
 bool operator>(hnod A)
    {return val>A.val;
    }
};

class minheap
{hnod h[NMAX];
 int SIZE;

 public:
     minheap()
     {int i; SIZE=0;
      for(i=0; i<NMAX; i++)
        {h[i].val=INF;
         h[i].key=-1;
        }
     }

     void sift(int pos)
     {int son;
      do
        {son=0;
         if(pos*2<=SIZE)
            {son=pos*2;
             if(pos*2+1<=SIZE && h[pos*2+1] < h[pos])
                son=pos*2+1;
             if(h[son] < h[pos])
                {hnod aux = h[pos];
                 h[pos] = h[son];
                 h[son] = aux;
                 pos = son;
                }
             else son=0;
            }
        }while(son);
     }

     void upheap(int pos)
     {hnod aux = h[pos];
      while(pos>1 && h[pos] < h[pos/2])
        {h[pos]=h[pos/2];
         h[pos/2]=aux;
         pos/=2;
        }
     }

     void push(int key, int val)
     {hnod aux;
      aux.key=key;
      aux.val=val;
      SIZE++;
      h[SIZE]=aux;
      upheap(SIZE);
     }

     void pop()
     {h[1]=h[SIZE];
      h[SIZE].key=-1;
      h[SIZE].val=INF;
      SIZE--;

      sift(1);
     }

     int top()
     {return h[1].key;
     }

     bool empty()
     {return SIZE==0;
     }
};

void dijkstra(int source)
{minheap h;
 int i, current, nod, cost;
 for(i=1; i<=nrnodes; i++)
    dist[i]=INF;
 dist[source]=0;

 h.push(source, 0);
 while(!h.empty())
    {current=h.top();
     for(i=0; i<G[current].size(); i++)
        {nod = G[current][i].target;
         cost = G[current][i].cost;

         if(dist[current] + cost < dist[nod])
            {dist[nod] = dist[current] + cost;
             h.push(nod, dist[nod]);
            }
        }
     h.pop();
    }
}

int main()
{Read();
 dijkstra(1);
 for(int i=2; i<=nrnodes; i++)
    w<<dist[i]<<" ";
 return 0;
}