ideia_07_01.cpp

// Ideias 07 - BFS 0-1

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
vector<pii> grafo[maxn];
int n, m, dist[maxn];

void dijkstra(int x) {
    memset(dist, 0x3f3f3f3f, sizeof dist); // Inicializando distancia como "infinito"

    dist[x] = 0;
    fila.push({dist[x], x});

    while (!fila.empty()) {
        int u = fila.top().second;
        fila.pop();

        for(int i = 0; i < (int)grafo[u].size(); i++) {
            int v = grafo[u][i].first;
            int d = grafo[u][i].second;
            if(dist[v] > dist[u] + d) {
                dist[v] = dist[u] + d;
                fila.push({dist[v], v});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int a, b, c;
        cin >> a >> b >> c;
        grafo[a].push_back({b, c});
        grafo[b].push_back({a, c});
    }

    dijkstra(1);
    cout << dist[n] << "\n";
    return 0;
}