关于全负权图最短路

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <cstring>
#include <sstream>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned int ui;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef unsigned long long ull;

#define rep(i, a, n) for(int i = (a); i <= (n); ++i)
#define per(i, a, n) for(int i = (a); i >= (n); --i)
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define mst(a, b) memset((a), (b), sizeof(a));
#define all(x) (x).begin(),(x).end()
#define tem template<class T> inline
#define sz(v) ((int)(v).size())
#define lowbit(x) (x & -x)
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define space putchar(' ')
#define enter puts("")
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define rd read()
#define ls (u << 1)
#define rs (u << 1 | 1)
const double eps = 1e-8;
const double pi = acos(-1.0);
ll sq(ll t) {return t * t;}
tem bool chmax(T &a, T b) {if(a < b) {a = b; return 1;} return 0;}
tem bool chmin(T &a, T b) {if(a > b) {a = b; return 1;} return 0;}
tem int sgn(T x) {return x > eps ? 1 : (x < -eps ? -1 : 0);}
ostream &operator << (ostream &os, const pii &p)
{return os << "(" << p.fi << ", " << p.se << ")";}
const int mod = 1e9 + 7;
const int N = 1e5 + 5;

int n, m, dis[N];
vector<pii> e[N];
bool vis[N];

struct event {
    int u, d;
    friend bool operator < (event a, event b) {return a.d > b.d;}
};

void dij(int s) {
    priority_queue<event> q;
    q.push({s, 0});
    mst(vis, 0);
    rep(i, 2, n) dis[i] = inf;
    while(!q.empty()) {
        int u = q.top().u; q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto [v, w] : e[u]) {
            if(dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                q.push({v, dis[v]});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    rep(i, 1, m) {
        int u, v, w; cin >> u >> v >> w;
        e[u].pb({v, -w});
    }
    dij(1);
    cout << (dis[n] == inf ? -1 : -dis[n]) << endl;
    return 0;
}