#include <fstream>
#include <vector>
#include <queue>
using namespace std;
struct nod
{
   int val, cost;
};
vector<nod> v[50005];
queue<int> q;
int d[50005];
int n, m, a, b, c;
int dijkstra(int x)
{
   bool ok = 0;
   for(int i = 2; i <= n; ++i)
      d[i] = (1 << 29);
   q.push(1);
   while(!q.empty()) {
      for(int i = 0; i < v[q.front()].size(); ++i) {
         if(d[q.front()] + v[q.front()][i].cost < d[v[q.front()][i].val]) {
            q.push(v[q.front()][i].val);
            d[v[q.front()][i].val] = d[q.front()] + v[q.front()][i].cost;
         }
      }
      if(q.front() == x) ok = 1;
      q.pop();
   }
   if(ok == 1) return d[x];
   return 0;
}
int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    in >> n >> m;
    for(int i = 1; i <= m; ++i) {
      nod d;
      in >> a >> b >> c;
      d.val = b;
      d.cost = c;
      v[a].push_back(d);
    }
    for(int i = 2; i <= n; ++i) out << dijkstra(i) << " ";
    return 0;
}