#include <fstream>
#include <list>
#include <climits>
#include <vector>
#include <algorithm>
#include <limits>

#define NODE(n) (n>>10)
#define COST(n) (n&1023)

std::ifstream in ("dijkstra.in");
std::ofstream out ("dijkstra.out");

std::vector<int> pos_in_heap;

class MinKupac
{
    private:
    std::vector<int> x;

    public:
    MinKupac()
    {
        x.resize(1);
        x[0] = std::numeric_limits<int>::max();
    }
    int meghat_min()
    {
        return x[1];
    }

    void fel (int p)
    {
        while (x[p] < x[p>>1] && p > 1) {
            std::swap (x[p], x[p>>1]);
            std::swap (pos_in_heap[x[p]], pos_in_heap[x[p>>1]]);
            p >>= 1;
        }
    }
    void le (unsigned p)
    {
        while (p << 1 <= x.size()-1) {
            if (x [p<<1] < x[p]) {
                p <<= 1;
                if (x[p+1] < x[p] && x[p+1] < x.size())
                    p++;
                std::swap (x[p], x [p>>1]);
                std::swap (pos_in_heap[x[p]], pos_in_heap [x [p>>1]]);
            }
            else if (x [(p<<1)+1] < x[p] && (p<<1)+1 < x.size()) {
                p = (p<<1) + 1;
                std::swap (x[p], x [p>>1]);
                std::swap (pos_in_heap[x[p]], pos_in_heap [x[p>>1]]);
            }
            else break;
        }
    }

    void betesz(int n)
    {
        x.push_back (n);
        pos_in_heap [n] = x.size()-1;
        fel (x.size()-1);
    }
    int kivesz_min()
    {
        int ret = this->meghat_min();
        pos_in_heap [x[1]] = 0;
        x[1] = x.back();
        x.pop_back();
        if (x.size() > 1) pos_in_heap [x[1]] = 1;
        le (1);
        return ret;
    }
    void csokkent (int pos, int uj)
    {
        pos_in_heap[x[pos]] = 0;
        x[pos] = uj;
        pos_in_heap[uj] = pos;
        fel (pos);
    }
    int meret()
    {
        return x.size()-1;
    }
};

int n, m;
std::vector< std::list<int> > x;
std::vector<int> path;

MinKupac Min;
void dijkstra (int node)
{
    int pos, newlen;
    std::list<int>::iterator i;

    path[node] = 0;
    Min.betesz (node);

    while (Min.meret()) {
        pos = Min.kivesz_min();
        for (i=x[pos].begin(); i!=x[pos].end(); i++) {
            newlen = path[pos] + COST(*i);
            if (path[NODE(*i)] == INT_MAX) {
                path[NODE(*i)] = newlen;
                Min.betesz (NODE(*i));
            }
            else if (newlen < path[NODE(*i)]) {
                path[NODE(*i)] = newlen;
                Min.csokkent (pos_in_heap[NODE(*i)], newlen);
            }
        }
    }
}

int main()
{
    in >> n >> m;

    x.resize (n+1);
    path.resize (n+1, INT_MAX);
    pos_in_heap.resize (n+1, 0);

    int a, b, c, i;
    for (i=0; i<m; i++) {
        in >> a >> b >> c;
        x[a].push_back ((b << 10) + c);
    }

    dijkstra (1);

    for (i=2; i<=n; i++) {
        if (path[i] != INT_MAX) out << path[i] << " ";
        else out << "0 ";
    }
}