ideia_07_02.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 bfs(int x) {
    memset(dist, 0x3f3f3f3f, sizeof dist); // Inicializando distancia como "infinito"

    dist[x] = 0;
    deque<int> fila;
    fila.push_back(x);

    while (!fila.empty()) {
        int u = fila.front();
        fila.pop_front();

        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;
                if(d == 1) fila.push_back(v); // Caso a distancia seja 1, insere o vertice normalmente na fila
                else fila.push_front(v); // Caso seja 0, insere como prioridade.
            }
        }
    }
}

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});
    }

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