#include <fstream>
#include <vector>
#include <queue>

const int NMAX = 50005;

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct muchie
{
    int y,d;

    bool operator < (const muchie &t) const
    {
        if (t.d < d)
            return true;
        return false;
    }

};

int N,M,x,y,cost;
int d[NMAX];
vector < pair <int, int> > v[NMAX];
priority_queue <muchie> Q;

void add(int nod)
{
    muchie M;

    for (int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i].first;
        int dist = v[nod][i].second;
        M.y = vecin;
        M.d = d[nod] + dist;
        if (!d[vecin])
            Q.push(M);
    }
}

void djk()
{
    d[1] = 1;
    add(1);

    muchie M;

    while (!Q.empty())
    {
        M = Q.top();
        Q.pop();

        if (d[M.y])
            continue;

        d[M.y] = M.d;
        add(M.y);
    }
}

int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        f >> x >> y >> cost;
        v[x].push_back(make_pair(y,cost));
    }

    djk();

    for (int i = 2; i <= N; ++i)
    {
        if (d[i] == 0)
            g << "0 ";
        else g << d[i]-1 << " ";
    }

    f.close();
    g.close();
    return 0;
}