#include <bits/stdc++.h>
#define input "dijkstra.in"
#define output "dijkstra.out"

using namespace std;


typedef vector <int> VI;
const int nmax = 50001;
const int inf = 1e9;

int n, m;
int d[nmax];
bool it[nmax];
vector <pair <int, int> > g[nmax];
struct cmp
{
    bool operator() (int x, int y)
    {
        return d[x] > d[y];
    }
};

priority_queue <int, VI, cmp> coada;

void dijk(int x)
{
    for (int i = 1; i <= n; ++i)
         d[i] = inf;
    d[x] = 0;
    coada.push(x);
    it[x] = true;
    while (!coada.empty())
    {
        int x = coada.top();
        coada.pop();
        it[x] = false;
        for (auto i : g[x])
          if (d[x] + i.second < d[i.first])
          {
              d[i.first] = d[x] + i.second;
              if (it[i.first] == false)
              {
                  coada.push(i.first);
                  it[i.first] = true;
              }
           }
    }
}

main()
{
    ifstream cin(input);
    ofstream cout(output);
    cin >> n >> m;
    for (; m ; --m)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back({y, z});
    }
    dijk(1);
    for (int i = 2; i <= n; ++i)
    {
        if (d[i] == inf) d[i] = 0;
        cout << d[i] << " ";
    }
}