#include <fstream>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;

ifstream is("dijkstra.in");
ofstream os("dijkstra.out");

struct Heap{
public:
    Heap(int);
    int top();
    bool inh(int x);
    bool Empty();
    void Swap(int x, int y);
    void push(int, int val);
    void up(int down);
    void pop(int poz);
    void down(int up);
    void change(int nod, int val);
private:
    int n, el;
    vector<int> h, nr, p;
};

void Heap::change(int nod, int val)
{
    nr[nod] = val;
    up(p[nod]);
}

bool Heap::inh(int x)
{
    return p[x];
}

bool Heap::Empty()
{
    return !n;
}

Heap::Heap(int x) : n(0), el(x)
{
    h.push_back(0);
    p = nr = vector<int>(x + 1);
}

int Heap::top()
{
    return h[1];
}

void Heap::Swap(int x, int y)
{
    swap(h[x], h[y]);
    swap(p[h[x]], p[h[y]]);
}

void Heap::push(int nod, int val)
{
    h.push_back(nod);
    p[nod] = ++n;
    nr[nod] = val;
    up(n);
}

void Heap::up(int down)
{
    int up = down / 2;
    while ( up && nr[h[up]] > nr[h[down]] )
    {
        Swap(up, down);
        down = up;
        up /= 2;
    }
}

void Heap::pop(int elem = 1)
{
    if ( p[elem] == n )
    {
        --n;
        h.pop_back();
        return;
    }
    h[p[elem]] = h[n--];
    p[h[p[elem]]] = p[elem];
    h.pop_back();
    down(p[elem]);
}

void Heap::down(int up)
{
    int down = 2 * up;
    while ( ( down <= n && nr[h[up]] > nr[h[down]] ) || ( down < n && nr[h[up]] > nr[h[down+ 1]] ) )
    {
        if ( down < n && nr[h[down]] > nr[h[down + 1]] )
            ++down;
        Swap(up, down);
        up = down;
        down *= 2;
    }
}

int main()
{
    int n, m, a, b, c;
    is >> n >> m;
    vector<int> d(n + 1, INF);
    vector<vector<pair<int, int>>> g(n + 1);
    while ( m-- )
    {
        is >> a >> b >> c;
        g[a].push_back(make_pair(c, b));
    }
    d[1] = 0;
    Heap h(n);
    h.push(1, 0);
    int nod;
    while ( !h.Empty() )
    {
        nod = h.top();
        h.pop();
        for ( const auto& nodv : g[nod] )
        {
            if ( d[nodv.second] > d[nod] + nodv.first )
            {
                d[nodv.second] = d[nod] + nodv.first;
                if ( !h.inh(nodv.second) )
                    h.push(nodv.second, d[nodv.second]);
                else
                    h.change(nodv.second, d[nodv.second]);
            }
        }
    }
    for ( int i = 2; i <= n; ++i )
        if ( d[i] == INF )
            os << "0 ";
        else
            os << d[i] << " ";
    is.close();
    os.close();
    return 0;
}