#include <fstream>
#include <queue>

using namespace std;

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

int N, M;
int D[50005];
vector<pair<int, int> > V[50005];

struct muchie
{
    int dist, nod;
    bool operator < (const muchie& m) const
    {
        if (m.dist <= dist)
            return true;
        return false;
    }
};
priority_queue<muchie> Q;

void add(int nod)
{
    muchie m;
    for (vector<pair<int, int> >::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
    {
        m.nod = it->first;
        m.dist = D[nod] + it->second;
        Q.push(m);
    }
}

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

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

        if (D[m.nod])
            continue;

        D[m.nod] = m.dist;
        add(m.nod);
    }
}

int main()
{
    fin >> N >> M;
    for (int i = 1, nod1, nod2, cost; i <= M; ++i)
    {
        fin >> nod1 >> nod2 >> cost;
        V[nod1].push_back(make_pair(nod2, cost));
    }

    djk();

    for (int i = 2; i <= N; ++i)
    {
        if (D[i] == 0)
            fout << 0 << ' ';
        else
            fout << D[i] - 1 << ' ';
    }
    fout << '\n';

    fin.close();
    fout.close();
    return 0;
}