使用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;
}