#include <bits/stdc++.h>

using namespace std;

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

class Edge
{
public:
    int node;
    int cost;

    Edge(int n, int c)
    {
        node = n;
        cost = c;
    }

    Edge()
    {}
};

class comp
{
public:
    bool operator()(Edge a, Edge b)
    {
        return a.cost > b.cost;
    }
};


vector <int> dijkstra(int start, int n, vector <vector <Edge>> &path, priority_queue<Edge, vector <Edge>, comp> &q, vector <bool> &viz)
{
    vector <int> dist(n + 1, numeric_limits<int>::max());

    q.push(Edge(start, 0));
    dist[start] = 0;

    for(Edge now, vec; !q.empty();)
    {
        now = q.top();
        q.pop();


        if(!viz[now.node])
        {
            for(unsigned i = 0; i < path[now.node].size(); i++)
            {
                vec = path[now.node][i];
                if(!viz[vec.node])
                {
                    dist[vec.node] = min(dist[now.node] + vec.cost, dist[vec.node]);
                    q.push(Edge(vec.node, dist[vec.node]));
                }
            }

            viz[now.node] = true;
        }
    }

    return dist;
}

int main()
{
    int n,m;
    fin>>n>>m;
    vector <vector <Edge>> path(n + 1);
    priority_queue <Edge, vector <Edge>, comp> q;
    vector <bool> viz(n, false);


    for(int x, y, c; m; m--)
    {
        fin>>x>>y>>c;
        path[x].push_back(Edge(y, c));
    }

    vector <int> ans = dijkstra(1, n, path, q, viz);

    for(int i = 2; i <= n; i++)
        fout<<ans[i]<<' ';
    fout<<'\n';

    return 0;
}