// Tenemos un vector<vector<pair<int,int> > > grafo donde los elementos del vector i son del estilo (distancia, vecino)

int dijkstra(int s, int dest){
    int n = grafo.size();
    const int INF = 100000000;
    vector<int> dist(n, INF);
    vector<int> prev(n, -1);
    vector<bool> vis(n, false);
    
    priority_queue< pair<int,int> , vector<pair<int,int> >, greater<pair<int,int> > > q;
    q.push(make_pair(0, s));
    dist[s]=0;
    while(!q.empty()){
        int nodoMasCercano=q.top().second;
        q.pop();
        if(!vis[nodoMasCercano]){
			vis[nodoMasCercano]=true;
			forn(i, grafo[nodoMasCercano].size()){
				int vecino = grafo[nodoMasCercano][i].second;
				int longitud = grafo[nodoMasCercano][i].first; // si guardaramos (vecino, distancia) esto sería al revés first y second
				int val = dist[nodoMasCercano]+longitud;
				if(val<dist[vecino]){
					dist[vecino]=val;
					prev[vecino]=nodoMasCercano;
					q.push(make_pair(val, vecino));
				}
			}
		}
    }
    // Imprimimos el camino, inverso. Para imprimirlo bien vamos guardando en un vector y lo imprimimos al revés
    int estoy = dest;
    cout<<estoy<<endl;
    while(estoy!=s){
        estoy=prev[estoy];
        cout<<estoy<<endl;
    }
    return dist[dest];
}