#define MAXN 
#define oo 1000000000

// *** floyd-warshall ***

// matrica u koju unosimo i u kojoj racunamo rezultate
int mat[MAXN][MAXN]; 
// broj cvorova
int n;
// broj bridova
int m;

void load_mat() {
    scanf("%d%d", &n, &m);
    
    // inicijalizacija matrice - dodajemo bridove beskonacne tezine
    for(int i = 0; i < MAXN; ++i)
        for(int j = 0; j < MAXN; ++j)
            if(i != j)
                mat[i][j] = oo;
       
    // unos, po bridovima
    for(int i = 0; i < m; ++i) {
        int prvi, drugi, tezina;
        scanf("%d%d%d", &prvi, &drugi, &tezina);
        mat[prvi][drugi] = mat[drugi][prvi] = tezina; // graf je neusmjeren
    }
}

void floyd() {
	// preko cvora k relaksiramo put od cvora i do cvora j
    for(int k = 0; k < n; ++k) 
        for(int i = 0; i < n; ++i) 
            for(int j = 0; j < n; ++j)
                mat[i][j] = min( mat[i][j], mat[i][k] + mat[k][j] );
}

// *** dijkstra ***
// http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

// edge[i] predstavlja sve veze iz cvora i, u obliku (drugi_cvor, tezina)
vector< vector< pair<int,int> > edge;

// broj cvorova
int n;

void load_list() {
    scanf("%d%d", &n, &m);

	// edge je sad n praznih vectora    
    edge.resize(n);
            
    for(int i = 0; i < m; ++i) {
        int prvi, drugi, tezina;
        scanf("%d%d%d", &prvi, &drugi, &tezina);
        edge[prvi].push_back( make_pair(drugi, tezina) );
    }
}

void dijkstra_spora() {
	// tu pamtimo rezultat, na pocetku je put do svakog cvora beskonacni
    vector<int> dist(n, oo);
	// ovdje pamtimo koje smo cvorove obradili
    vector<int> bio(n, 0);
	
    dist[0] = 0; 
    
	// back[i] predstavlja cvor iz kojeg smo dosli u cvor i, u optimalnom rjesenju, radi rekonstrukcije
	// sjetite se stabla s predavanja :)
    vector<int> back(n);
    
    for(int i = 0; i < n-1; ++i) {
		// trazimo najblizi cvor koji nismo obradili
        int next = -1;
        for(int j = 0; j < n; ++j)
            if(!bio[j] && (next == -1 || dist[next] > dist[j]))
                next = j;
        
        bio[next] = 1;
        
        // relaksacija
        for(int j = 0; j < (int)edge[next].size(); ++j) {
            int c = edge[next][j].first;
            int d = edge[next][j].second;
            if(dist[next] + d < dist[c] ) {
                dist[c] = dist[next] + d; 	// relaksiramo put do c
                back[c] = next; 			// pamtimo povratnu vezu (rekonstrukcija)
            }
        }
    }
    
    // rekonstrukcija, krecemo od kraja (u ovom slucaju cvor n-1) prema pocetku (cvor 0)
    vector<int> rezultat;
    int temp = n-1;
    while(temp != 0) {
        rezultat.push_back(temp);
        temp = back[temp];
    }
    rezultat.push_back(0);

	// posto idemo od kraja prema pocetku, treba okrenut vector
    reverse(rezultat.begin(), rezultat.end());
    
    
}

// brza dijkstra radi tako da imamo set (balansirano binarno stablo) u kojem pamtimo neobradjene cvorova
// umjesto da obilazimo sve cvorove, samo iz seta pocupamo najblizi neposjeceni cvor
void dijkstra_brza() {
	// tu opet pamtimo rezultat
    vector<int> dist(n, oo);
	// ovdje pamtimo parove (tezina, cvor) neposjecenih cvorova
	// tezina je prva jer zelimo da po njoj sortira
    set< pair<int,int> > Q;
    
	// inicijaliziramo dijkstru
    dist[0] = 0;
    Q.insert( make_pair(0, 0) );
    
	// petlja se vrti dok god ima necega u setu, ako graf nije povezan, onda se neke tocke uopce nece tu naci
    while(!Q.empty()) {
		// uzmemo i izbrisemo najblizi
        pair<int,int> prvi = *Q.begin();
        int pivot_d = prvi.first;
        int pivot_n = prvi.second;
        Q.erase(Q.begin());
        
        for(int i = 0; i < (int)edge[next].size(); ++i) {
            int next_d = edge[next][i].second;
            int next_n = edge[next][i].first;
            
            if(pivot_d + next_d < dist[next_n]) {
				// ako je uopce cvor koji relaksiramo u setu, treba ga izbrisati
                if(dist[next_n] != oo) {
                    Q.erase( Q.find( make_pair( dist[next_n], next_n ) ) );
                }
                
				// racunaj udaljenost
                dist[next_n] = pivot_d + next_d;
				// ubaci novu vrijednost u set
                Q.insert( make_pair( dist[next_n], next_n ) );
            }
            
        }
    }
}

// za detalje o setu i ostalim strukturama u c++, preporucam pogledati STL dokumentaciju (www.sgi.com/tech/stl), kao i Osvaldov tutorial kojeg mozete naci na materijalima (fer2)