#include <fstream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

typedef pair<int, int>  ii;
typedef vector<int>     vi;
typedef vector<ii>      vii;

const int INFINIT = 1 << 30;


struct cmp_less
{
    bool operator()(const ii &a, const ii &b) const
    {
        return (a.second < b.second);
    }
};


void Dijkstra(int start, const vector<vii> &Neighbors, vi &D)
{
    set<ii, cmp_less> S;

    fill(D.begin(), D.end(), INFINIT);
    D[start] = 0;
    S.insert(make_pair(start, 0));

    while (!S.empty())
    {
        int node = S.begin()->first;

        S.erase(S.begin());
        for (vii::const_iterator it = Neighbors[node].begin(); it != Neighbors[node].end(); it++)
        {
            int neigh   = it->first;
            int w       = it->second;

            if (D[neigh] > D[node] + w)
            {
                if (D[neigh] != INFINIT) S.erase(S.find(make_pair(neigh, D[neigh])));
                D[neigh] = D[node] + w;
                S.insert(make_pair(neigh, D[neigh]));
            }
        }
    }
}


int main()
{
    fstream         f, g;
    vector< vii >   Neighbors;
    vi              D;
    int             N, M;

    f.open("dijkstra.in", ios::in);
    g.open("dijkstra.out", ios::out);

    f >> N >> M;
    Neighbors.resize(N);
    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        f >> a >> b >> c;
        a--;b--;
        Neighbors[a].push_back(make_pair(b, c));
    }

    D.resize(N);
    Dijkstra(0, Neighbors, D);

    for (int i = 1; i < N; i++)
    {
        g << ((D[i] == INFINIT) ? 0 : D[i]) << " ";
    }

    f.close();
    g.close();

    return 0;
}