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

using namespace std;

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

struct muchie
{
    int nod, d;

    bool operator < (const muchie& m) const
    {
        if (m.d < d) return true;
        return false;
    }
};
priority_queue<muchie> Q;

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

void add(int nod)
{
    muchie m;
    for (vector<pair<int, int> >::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
    {
        if (!D[it->first])
        {
            m.nod = it->first;
            m.d = 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.d;
        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;
}