#include vector
#include fstream
#include utility
#include queue
  
using namespace std;
  
int vizitat[50010], distanta[50010];
  
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
  
    int i;
    int nr_noduri, nr_muchii, nod_plecare, nod_destinatie, pondere, nod_curent, nod_aux, cost;
  
    vectorpairint,int  graf[50001];
    pairint,int pereche;
    queueint coada;
  
    f  nr_noduri  nr_muchii;
  
    for(i = 0; i  nr_muchii; i++)
        {
            f  nod_plecare  nod_destinatie  pondere;
            pereche = make_pair(nod_destinatie,pondere);
  
            graf[nod_plecare].push_back(pereche);
        }
  
    distanta[1] = 0;
    for(i = 2; i = nr_noduri; i++)
        distanta[i] = 9999;
  
    coada.push(1);
    vizitat[1] = 0;
    while(!coada.empty())
        {
            nod_curent = coada.front();
            vizitat[nod_curent] = 0;
            coada.pop();
  
            for(i = 0; i  graf[nod_curent].size(); i++)
                {
                    nod_aux = graf[nod_curent][i].first;
                    cost = graf[nod_curent][i].second;
  
                    if(distanta[nod_aux]  distanta[nod_curent] + cost)
                        {
                            distanta[nod_aux] = distanta[nod_curent] + cost;
                            if(!vizitat[nod_aux])
                                {
                                    vizitat[nod_aux] = 1;
                                    coada.push(nod_aux);
                                }
                        }
                }
        }
  
    for(i = 2; i = nr_noduri; i++)
        if(distanta[i] == 9999)
            g  0   ;
        else
            g  distanta[i]   ;
  
    return 0;
}