使用dijkstra堆优化，本题有环，卡dp。 dijkstra朴素版可能会被卡数据范围。 链式前向星 板子题，学到这里的应该属于送分题。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>
#include <iomanip>
#include <stack>
#include <bitset>

#define int long long
#define PII pair<int, int> 
#define TLLL tuple<int , int , int>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f
#define all(v) v.begin() + 1 , v.end()
#define ALL(v) v.begin() , v.end()
#define endl "\n"
using namespace std;
const int N = 2e5 + 10;
int e[N] , w[N] , ne[N] , dist[N] , h[N] , idx;
bool st[N];

inline void add(int a , int b , int c)
{
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++;
    return ;
}

void dijkstra()
{
    memset(dist , inf , sizeof dist);
    memset(st , false , sizeof st);

    priority_queue<PII , vector<PII> , greater<PII> > heap;

    dist[1] = 0;
    heap.push({0 , 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int distance = t.first , index = t.second;

        if (st[index]) continue;
        st[index] = true;

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];

            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j] , j});
            }
        }
    }
}

void solve()
{
    memset(h , -1 , sizeof h);
    int n , m;
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i ++ )
    {
        int a , b , c;
        cin >> a >> b >> c;
        add(a , b , c);
    }
    dijkstra();

    if (dist[n] >= INF / 2) cout << -1 << endl;
    else cout << dist[n] << endl;
    return ;
}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T -- ) solve();
    return 0;
}

#include <bits/stdc++.h>
// #define int long long // 仅在需要大整数时使用，memset 数组为 0x3f 时去掉
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define ULL unsigned long long
#define PIII tuple<int, int, int>
#define all(v) v.begin(), v.end()
#define debug(a) cout << #a << " = " << a << endl;
using namespace std;
constexpr int N = 1 * 1e5 + 10, M = 2 * 1e5 + 10;

int n, m;
vector<PII> G[M];
int dist[N];
bool st[N]; 
int Dijikstra() {
    memset(dist, 0x3f, sizeof(dist));
    memset(st, false, sizeof(st));
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push(make_pair(0, 1));
    dist[1] = 0;
    while (heap.size()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (st[u]) continue;
        st[u] = 1;
        for (auto [v, w] : G[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                heap.push(make_pair(dist[v], v));
            }
        }
    }
    return dist[n];
}
void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].emplace_back(v, w);
    }

    int ans = Dijikstra();
    if (ans >= INF / 2) cout << -1 << '\n';
    else cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    description: C++17 Algorithm Template for Competitive Programming
 */