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

using namespace std;

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

const int oo = 1e9 + 5;

struct NodeCost
{
    int node, cost;

    bool operator < (const NodeCost other) const{
        return this->cost > other.cost;
    }
};

priority_queue <NodeCost> pq;
vector <NodeCost> g[50005];
int N, M, dist[50005];

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= N; i++)
        dist[i] = oo;

    int x, y, z;
    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y >> z;
        NodeCost nc;
        nc.node = y, nc.cost = z;

        g[x].push_back(nc);
    }

    NodeCost nc;
    nc.node = 1, nc.cost = 0;
    pq.push(nc);

    while(!pq.empty())
    {
        int currentNode = pq.top().node, currentCost = pq.top().cost;
        pq.pop();

        if(dist[currentNode] != oo)
            continue;

        dist[currentNode] = currentCost;
        for(auto muchie : g[currentNode])
        {
            int vecin = muchie.node;
            int costMuchie = muchie.cost;

            if(dist[vecin] == oo)
            {
                NodeCost nc;
                nc.node = vecin;
                nc.cost = currentCost + costMuchie;

                pq.push(nc);
            }
        }
    }

    for(int i = 2; i <= N; i++)
        fout << ((dist[i] == oo) ? 0 : dist[i]) << ' ';

    return 0;
}