#include <fstream>
#include <queue>
using namespace std;

int varfuri, muchii, D[50005];
bool viz[50005];
vector<pair<int,int>> G[50005];

struct compara
{
    bool operator()(int x, int y)
    {
        return D[x] > D[y];
    }
};
priority_queue<int, vector<int>, compara> qu;

void Dijkstra(int nodStart)
{
    for (int i = 1; i <= varfuri; ++i)
        D[i] = 2000001;

    D[nodStart] = 0;
    qu.push(nodStart);
    viz[nodStart] = true;
    while (!qu.empty())
    {
        int nodCurent = qu.top();
        qu.pop();

        viz[nodCurent] = false;
        for (unsigned int i = 0; i < G[nodCurent].size(); ++i)
        {
            int vecin = G[nodCurent][i].first;
            int cost = G[nodCurent][i].second;
            if (D[nodCurent] + cost < D[vecin])
            {
                D[vecin] = D[nodCurent] + cost;
                if (!viz[vecin])
                {
                    qu.push(vecin);
                    viz[vecin] = true;
                }
            }
        }
    }
}

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin >> varfuri >> muchii;

    for (int i = 1; i <= muchii; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }

    Dijkstra(1);

    for (int i = 2; i <= varfuri; ++i)
        if (D[i] != 2000001)
            fout << D[i] << " ";
        else
            fout << "0 ";
}