#include <bits/stdc++.h>

using namespace std;

class Node
{
    // variables
public:
    int node;
    int cost;
private:
    // functions

public:

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

    Node()
    {}

    Node(int n, int c)
    {
        initialize(n, c);
    }

    ~Node()
    {}
private:

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

};

vector <int> dijkstra(int start, vector <vector <Node>> &path)
{
    vector <int> dist(path.size(), numeric_limits<int>::max());
    priority_queue <Node, vector <Node>, comp> q;

    dist[start] = 0;
    Node current, vec;
    q.push(Node(start, 0));

    while(!q.empty())
    {
        current = q.top();
        q.pop();
        cout<<current.node<<' '<<dist[current.node]<<'\n';

        for(unsigned i = 0; i < path[current.node].size(); i++)
        {
            vec = path[current.node][i];
            if(dist[vec.node] == numeric_limits<int>::max())
            {
                dist[vec.node] = dist[current.node] + vec.cost;
                q.push(Node(vec.node, dist[vec.node]));
            }
        }
    }

    return dist;
}

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

int main()
{
    int n, m;
    fin>>n>>m;
    vector < vector <Node>> path(n + 1);


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

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

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

    return 0;
}