#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

using VI = vector<int>;
using VP = vector<pair<int, int>>;
using VVI = vector<VI>;
using VVP = vector<VP>;

class Heap{ // minHeap
public:
    Heap(int N = 0, const VI& D = VI(1))
        : nH{0},
          H{VI(N + 1)},
          P{VI(N + 1)},
          D{D}
    {}

    void pop(int node = 1)
    {
        Swap(nH, node);
        --nH;

        int son{2 * node};
        while (son <= nH)
        {
            if (son < nH &&
                (D[H[son]] > D[H[son + 1]]))
                ++son;

            if (D[H[son]] < D[H[node]])
            {
                Swap(son, node);
                node = son;
                son = 2 * node;
            }
            else
                break;
        }
    }

    void up(int node)
    {
        int t = node / 2;

        while (t)
        {
            if (D[H[t]] > D[H[node]])
            {
                Swap(t, node);
                node = t;
                t = node / 2;
            }
            else
                break;
        }
    }

    void push(int node)
    {
        H[++nH] = node;
        P[node] = nH;

        up(node);
    }

    int top() const
    {
        return H[1];
    }

    bool empty() const
    {
        return nH <= 0;
    }

private:
    void Swap(int x, int y)
    {
        swap(H[x], H[y]);
        P[H[x]] = x;
        P[H[y]] = y;
    }

    int nH;
    VI H, P;
    const VI& D;
};

const int Inf = 0x3f3f3f3f;

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

int N, M;
VVP G;
VI D;

void ReadGraph();
void Dijkstra(int node = 1);
void Write(int node = 1);

int main()
{
    ReadGraph();
    Dijkstra();
    Write();

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

void ReadGraph()
{
    fin >> N >> M;
    G = VVP(N + 1);

    int x, y, w;
    while (M--)
    {
        fin >> x >> y >> w;
        G[x].push_back({y, w});
    }
}

void Dijkstra(int node)
{
    D = VI(N + 1, Inf);
    Heap H{N, D};

    D[1] = 0;
    H.push(1);

    while (!H.empty())
    {
        int n = H.top();
        H.pop();

        for (const pair<int, int>& v : G[n])
            if (D[v.first] > D[n] + v.second)
            {
                bool inHeap = D[v.first] != Inf;
                D[v.first] = D[n] + v.second;

                if (inHeap)
                    H.up(v.first);
                else
                    H.push(v.first);
            }
    }
}

void Write(int node)
{
    for (int i = 1; i <= N; ++i)
        if (i != node)
        {
            if (D[i] < Inf)
                fout << D[i] << ' ';
            else
                fout << 0 << ' ';
        }
}