#include <fstream>
#include <vector>
#include <set>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int INF = 99999999;

struct arc
{
    int vf;
    int cost;

    friend bool operator < (const arc &src1, const arc &src2)
    {
        return src1.cost < src2.cost;
    }
};

set<arc> heap;

arc minFromSet()
{
    return *(heap.begin());
}
void insertArcInSet(int to, int cost)
{
    arc a;
    a.vf = to;
    a.cost = cost;
    heap.insert(a);
}
void eraseArcFromSet(int to, int cost)
{
    arc a;
    a.vf = to;
    a.cost = cost;
    heap.erase(a);
}

vector<arc> v[50010];

int d[50010], n, m;

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

    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        arc aux;
        aux.vf = y;
        aux.cost = c;
        v[x].push_back(aux);
    }
    int init = 1;
    for(int i = 0 ; i <= n + 1; i++)
    {
        d[i] = INF;
    }

    int l = v[init].size();
    d[init] = 0;

    insertArcInSet(init, 0);
    for(int i = 1; i <= n - 1; i++)
    {
        arc cmin = minFromSet();
        int vf = cmin.vf;
        heap.erase(cmin);
        l = v[vf].size();
        for(int j = 0; j < l; j++)
        {
            int vc = v[vf][j].vf;
            int dist = v[vf][j].cost;
            if(d[vf] + dist < d[vc])
            {
                if (d[vc] != INF)
                {
                    eraseArcFromSet(vc, d[vc]);
                }
                d[vc] = d[vf] + dist;
                insertArcInSet(vc, d[vc]);
            }
        }
    }

    for(int i = 2; i <= n; i++)
    {
        fout << ((d[i] == INF) ? 0 : d[i] ) << ' ';
    }

    return 0;
}