#include <bits/stdc++.h>
#define nmax 50005

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


struct cmp
{
    bool operator() (const pair <int, int> &a, const pair <int, int> &b) const
    {
        return a.second > b.second;
    }
};

priority_queue <pair <int, int>, vector<pair <int, int> >, cmp > heap;
vector <pair <int, int> >vec[nmax];
int dis[nmax];
const int oo = (1 << 30);

int main()
{
   int n, m;
   f >> n >> m;
   for (int i = 2; i <= n; ++ i)
       dis[i] = oo;
   dis[1] = 0;
   while (m --)
   {
       int x, y, c;
       f >> x >> y >> c;
       vec[x].emplace_back(y, c);
   }
   heap.push({1, dis[1]});
   while (!heap.empty())
   {
       pair <int, int> nod = heap.top();
       heap.pop();
       if (dis[nod.first] != nod.second)
           continue;
       for (auto next : vec[nod.first])
           if (dis[next.first] > nod.second + next.second)
           {
               dis[next.first] = nod.second + next.second;
               heap.push({next.first, dis[next.first]});
           }
   }
   for (int i = 2; i <= n; ++ i)
       if (dis[i] == oo)
           g << 0 << " ";
       else
           g << dis[i] << " ";
}