Dijkstra - Single Source Shortest Path

//pb : https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B#
#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
typedef pair<ll,ll> pll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL))
#define fi first
#define se second
#define pb push_back
ll const MOD=1000000007;

const int M=100005;

#define eb emplace_back

vector<pll>adj[M+10];

ll n,m;


ll cost[M+1];


void Dijkstra(ll s)
{


   priority_queue<pll,vector<pll>,greater<pll>>q;


   for(ll i=0;i<=M;i++)
   {
       cost[i]=1e8;
   }

   q.push({0,s});
    cost[s]=0;

   while(!q.empty())
   {
         ll u=q.top().se;
          q.pop();

          for(auto x:adj[u])
          {
              ll v=x.fi;
              ll w=x.se;

              if(cost[u]+w<cost[v])
              {
                  cost[v]=cost[u]+w;
                  q.push({cost[v],v});
              }


          }
   }


}
void input()
{
     cin>>n;

    ll a,b,w;

    for(ll i=1;i<=n;i++)
    {
        ll k;

       cin>>a>>k;

       while(k--)
       {
           cin>>b>>w;

             adj[a].eb(b,w);

      // v[b].eb(a,w);
       }


    }
}
int main()
{
    fastread();

    input();

   //fill(cost,cost+n+2,1e9);

    Dijkstra(0);

    for(ll i=0; i<n; i++)
    {
        cout<<i<<" "<<cost[i]<<endl;
    }





}