#include <bits/stdc++.h>

using namespace std;

const int oo = 1e9;
const int dim = 50005;




struct Weighted_edges
{
    int node, weight;
    bool operator < (const Weighted_edges A) const
    {
        return weight < A.weight;
    }
};

template <class T>
class Graph
{
private:
    int node_count, edge_count;
    vector <T> adj[dim];
    vector <T> r_adj[dim];
public:
    Graph ()
    {
        node_count = 0;
        edge_count = 0;
    }
    void Make_Graph (int nodes, int edges)
    {
        node_count = nodes;
        edge_count = edges;
    }
    void Add_edge (int node1, int node2)
    {
        adj[node1].push_back(node2);
    }
    void Add_reverse_edge (int node1, int node2)
    {
        r_adj[node2].push_back(node1);
    }
    void Add_weighted_edge(int node1, int node2, int weight)
    {
        adj[node1].push_back({node2, weight});
    }
    int NodeNumber ()
    {
        return node_count;
    }
    void Afis_Graph ()
    {
        for (int i = 1; i <= node_count; i++, cout << "\n")
        {
            cout << i << ": ";
            for (int j : adj[i])
                cout << j << " ";
        }
    }
    void DFS_SortTop (int node, vector <int> &viz, stack <int> &st)
    {
        viz[node] = 1;
        for (int i : adj[node])
            if (!viz[i])
                DFS_SortTop(i, viz, st);
        st.push(node);
    }
    void DFS_SCC (int node, vector <int> &viz, vector <int> scc[dim], int nrscc)
    {
        viz[node] = 0;
        for (int i : r_adj[node])
            if (viz[i])
                DFS_SCC(i, viz, scc, nrscc);
        scc[nrscc].push_back(node);
    }
    stack <int> SortTop (vector <int> &viz, stack <int> &st)
    {
        for (int i = 1; i <= node_count; i++)
            if (!viz[i])
            {
                DFS_SortTop(i, viz, st);
            }
        return st;
    }
    void SCC(ofstream &fout, vector <int> &viz, stack <int> &st)
    {
        int nrscc = 0;
        stack <int> sol = SortTop(viz, st);
        vector <int> scc[dim];
        while (!sol.empty())
        {
            int node = sol.top();
            sol.pop();
            if (viz[node] == 1)
            {
                nrscc++;
                DFS_SCC(node, viz, scc, nrscc);
            }
        }
        fout << nrscc << "\n";
        for (int i = 1; i <= nrscc; i++)
        {
            for (int j : scc[i])
                fout << j << " ";
            fout << "\n";
        }
    }
    vector <int> Dijkstra (vector <int> &viz, vector <int> &d, int start)
    {
        priority_queue <Weighted_edges> q;
        for (int i = 1; i <= node_count; i++)
            d[i] = oo;
        d[start] = 0;
        q.push({start, 0});
        while (!q.empty())
        {
            int node = q.top().node;
            q.pop();
            if (viz[node] == 0)
            {
                viz[node] = 1;
                for (auto i : adj[node])
                {
                    if (d[i.node] > d[node] + i.weight)
                    {
                        d[i.node] = d[node] + i.weight;
                        q.push({i.node, -d[i.node]});
                    }
                }
            }
        }
        return d;
    }

};

vector <int> viz(dim);
vector <int> d(dim);
stack <int> st;
Graph <int> G;
Graph <Weighted_edges> G2;

void Solve_SortTop()
{
    ifstream fin ("sortaret.in");
    ofstream fout ("sortaret.out");
    Graph <int> G;
    int n , m;
    fin >> n >> m;
    G.Make_Graph(n , m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        G.Add_edge(x, y);
    }
    stack <int> sol;
    sol = G.SortTop(viz, st);
    while (!sol.empty())
    {
        fout << sol.top() << " ";
        sol.pop();
    }
}


void Solve_SCC()
{
    ifstream fin ("ctc.in");
    ofstream fout ("ctc.out");
    int n, m;
    fin >> n >> m;
    G.Make_Graph(n, m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        G.Add_edge(x, y);
        G.Add_reverse_edge(x, y);
    }
    G.SCC(fout, viz, st);
}


void Solve_Dijkstra()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    int n, m;
    fin >> n >> m;
    G2.Make_Graph(n, m);
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G2.Add_weighted_edge (x, y, c);
    }
    vector <int> sol = G2.Dijkstra(viz, d, 1);
    for (int i = 2; i <= n; i++)
        if (d[i] != 1e9)
            fout << d[i] << " ";
        else fout << "0 ";
    fout << "\n";
}

int main()
{
    Solve_Dijkstra();
    return 0;
}