1148.cpp

#include <bits/stdc++.h>
#define inf 1e9

using namespace std;

typedef pair<int, int> ii;

void djikstra(vector<pair<int, int> > grafo[], int start){
	priority_queue<ii, vector<ii>, greater<ii> > PQ;
	PQ.push(make_pair(0, start)); 

	while (!PQ.empty()){
		custo = PQ.top().first;
		cidade = PQ.top().second;
		PQ.pop();
		
		if (custo < dist[start][cidade]){ 
			dist[start][cidade] = custo;
		}

		for (int i=0; i<grafo[cidade].size(), i++){
			PQ.push(make_pair(grafo[i].first, grafo[i].second)); // primeiro eh o custo
		}
	}

	for (int i=0; i<verts; i++){
		if (dist[start][i] == 1e9){
			dist[start][i] = -1;
		}
	}
}



int main(){
	int verts, edges, de, para, custo; // passar verts como parametro de djikstra
	while (scanf("%d %d", &verts, &edges)){
		if (!verts or !edges) break;
		verts++;

	 	int dist[verts][verts];
		memset(dist, inf, sizeof(dist)); 
		vector<pair<int, int> > grafo[verts+1];

		for (int i=0; i<edges; i++){
			scanf("%d %d %d", &de, &para, &custo);

			for (int k=0; k<grafo[para].size(); k++){
				if (grafo[para][k].second == de) {
					grafo[para][k].first = 0;
					custo = 0;
				}
			}

			grafo[de].push_back(make_pair(custo, para));
		}	

		int k;
		for (int i=0; i<k; i++){
			scanf("%d %d", &de, &para);
			if (dist[de][para] == 1e9) djikstra(grafo, de);
			if (dist[de][para] == -1){ printf("Nao e possivel entregar a carta\n");
			} else {
				printf("%d\n", dist[de][para]);
			}
		}
	}





	return 0;
}