#include <bits/stdc++.h>

using namespace std;

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

#define INTMAX 210000000

typedef pair<int,int> intPair;
priority_queue<intPair, vector<intPair>, greater<intPair>> pq;
int distances[1001],visited[1001];
vector<vector<intPair>> edges;

int main()
{
    int nrNodes, nrEdges, node1, node2, weight;
    f>>nrNodes>>nrEdges;

    for(int i=1; i<=1001; i++)
        edges.push_back(vector<intPair>());
    for(int i=1; i<=nrEdges; i++)
    {
        f>>node1>>node2>>weight;
        edges[node1].push_back(make_pair(node2,weight));
    }

    int sourceNode = 1, currentNode;
    distances[1]=0;
    for(int i=2; i<=nrNodes; i++)
        distances[i] = INTMAX;

    pq.push(make_pair(0,1)); ///(key, nod)
    while(!pq.empty())
    {
        currentNode = pq.top().second;

        pq.pop();
        visited[currentNode]++;
        if(visited[currentNode]==1)
            for(int i=0; i<edges[currentNode].size(); i++)
            {
                int nodeAdjacent = edges[currentNode][i].first;

                int weightTo = edges[currentNode][i].second;

                if(distances[nodeAdjacent] > distances[currentNode] + weightTo)
                {
                    distances[nodeAdjacent] = distances[currentNode] + weightTo;
                    pq.push(make_pair(distances[nodeAdjacent],nodeAdjacent));
                }

            }
    }
    for(int i=2; i<=nrNodes; i++)
        cout<<i<<' '<<distances[i]<<endl;
    return 0;
}