#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct nod
{
   int val, cost;
};
vector<nod> v[50005];
queue<int> q;
int d[50005];
bool viz[50005];
int n, m, a, b, c;

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)
      d[i] = (1<<29);
    int np = 1, nrviz = 0;
    for(int i = 1; i <= n; ++i)
    {
        int mind = (1<<29);
        for (int j = 1; j <= n; ++j)
            if (d[j] < mind && !viz[j])
                mind = d[j], np = j;
        viz[np] = 1;
        for(int j = 0; j < v[np].size(); ++j) {
          if(d[v[np][j].val] > d[np] + v[np][j].cost)
            d[v[np][j].val] = d[np] + v[np][j].cost;
        }
    }
    for(int i = 2; i <= n; ++i) out << d[i] << " ";
    return 0;
}