#include<iostream>
#include<queue>
#include<list>
#include<cstring>
#define INF 0x3f3f3f3f
#define iPair pair<int, int>
using namespace std;
class Graph{

int V;
list<iPair>*Adj;

public:Graph(int v){
this->V=v;
Adj=new list<iPair>[v];
}

public:addEdge(int u, int v, int weight){
Adj[u].push_back(make_pair(v, weight));
Adj[v].push_back(make_pair(u, weight));
}

public:dij(int s){

priority_queue<iPair, vector<iPair>, greater<iPair> > pq;
int dist[this->V];
memset(dist, INF, this->V);
pq.push(make_pair(0, s));
dist[s]=0;
list<iPair>::iterator i;

while(!pq.empty()){
int q=pq.top().second;
pq.pop();
for(i=Adj[q].begin();i!=Adj[q].end();i++){

int v=(*i).first;
int weight=(*i).second;

if(dist[v]>dist[q]+weight){
dist[v]=dist[q]+weight;
pq.push(make_pair(dist[v], v));
}
}
}

for(int i=0;i<this->V;i++){
cout<<i<<" "<<dist[i]<<'\n';
}

}
};

int main(){
int V=9;
Graph g(V);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
g.dij(0);
}