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

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int inf = 0x3f3f3f3f;
int N, M;
vector <pair<int, int>> G[50002];
vector <int> Dist, In_Queue;

void bellmanford(int node)
{
    Dist[node] = 0;
    queue <int> Q;
    Q.push(node);
    In_Queue[node] = 1;
    while (!Q.empty())
    {
        int current_node = Q.front();
        Q.pop();
        In_Queue[current_node] = 0;
        for (const pair <int,int> p : G[current_node])
            if (Dist[p.first] > Dist[current_node] + p.second)
            {
                Dist[p.first] = Dist[current_node] + p.second;
                if (In_Queue[p.first] == 0)
                {
                    Q.push(p.first);
                    In_Queue[p.first] = 1;
                }
            }
    }
}

int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back({y, c});
    }
    Dist = vector <int> (N + 1, inf);
    In_Queue = vector <int> (N + 1);
    bellmanford(1);
    for (int i = 2; i <= N; ++i)
        if (Dist[i] != inf)
            g << Dist[i] << " ";
        else
            g << "0 ";
    f.close();
    g.close();
    return 0;
}