#include <fstream>
#include <vector>
#define mp make_pair
#define INF 0x3f3f3f3f
#define nodv g[nod][i].second
#define costm g[nod][i].first
using namespace std;

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

int n, m;
vector<int> d;
vector<vector<pair<int, int> > > g;

struct Heap{
    Heap(int _n = 0) : nrh(0)
    {
        h = vector<int>(_n + 1);
        poz = vector<int>(_n + 1, 0);
    }
    bool empty()
    {
        return nrh ? 0 : 1;
    }
    bool inh(int nod)
    {
        return poz[n] ? 1 : 0;
    }
    int top()
    {
        return h[1];
    }
    void down(int up)
    {
        int down = 2 * up;
        while ( ( down <= nrh && d[h[up]] > d[h[down]] ) || ( down < nrh && d[h[up]] > d[h[down + 1]] ) )
        {
            if ( down < nrh && d[h[down + 1]] < d[h[down]] )
                ++down;
            swap(poz[h[up]], poz[h[down]]);
            swap(h[up], h[down]);
            up = down;
            down *= 2;
        }
    }
    void up(int down, int nr = 1)
    {
        int up = down / 2;
        while ( up && d[h[up]] > d[h[down]] )
        {
            swap(poz[h[up]], poz[h[down]]);
            swap(h[up], h[down]);
            up /= 2;
            down /= 2;
            Heap::down(down);
        }
    }
    void push(int nod)
    {
        poz[nod] = ++nrh;
        h[nrh] = nod;
        up(nrh);
    }
    void pop(int pozitie = 1)
    {
        poz[h[pozitie]] = 0;
        h[pozitie] = h[nrh--];
        poz[h[pozitie]] = pozitie;
        down(pozitie);
    }
    void change(int nod)
    {
        up(poz[nod], 2);
    }
    int nrh;
    vector<int> h, poz;
};

void Read();
void Dijkstra();
void Write();

int main()
{
    Read();
    Dijkstra();
    Write();
    is.close();
    os.close();
    return 0;
}

void Dijkstra()
{

    d = vector<int>(n + 1, INF);
    d[1] = 0;
    Heap h(n);
    h.push(1);
    int nod, cost;
    while ( !h.empty() )
    {
        nod = h.top();
        h.pop();
        for ( size_t i = 0; i < g[nod].size(); ++i )
        {
            if ( d[nodv] > d[nod] + costm )
            {
                d[nodv] = d[nod] + costm;
                if ( h.inh(nodv) )
                    h.change(nodv);
                else
                    h.push(nodv);
            }
        }
    }
}

void Read()
{
    is >> n >> m;
    g = vector<vector<pair<int, int> > >(n + 1);
    int n1, n2, cost;
    while ( m-- )
    {
        is >> n1 >> n2 >> cost;
        if ( n2 != 1 )
            g[n1].push_back(mp(cost, n2));
    }
}

void Write()
{
    for ( int i = 2; i <= n; ++i )
        d[i] != INF ? os << d[i] << " " : os << "0 ";
}