Bellman Ford

/*
    Task    : Bellman Ford
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 30 July 2022 [11:03]
*/
#include<bits/stdc++.h>
using namespace std;
struct A{
    int  u,v,w;
};
vector<A > edges;
int dis[100010],dis2[100010];
int main(){
    int n,m,u,v,w;
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&u,&v,&w);
        edges.push_back({u,v,w});
    }
    dis[0] = 0;
    for(int i=1;i<n;i++)
        dis[i] = 1e9;
    for(int i=1;i<=n-1;i++)
        for(auto x:edges)
            if(dis[x.u] + x.w < dis[x.v])
                dis[x.v] = dis[x.u] + x.w;

    for(int i=0;i<n;i++)
        dis2[i] = dis[i];
    for(auto x:edges)
        if(dis[x.u] + x.w < dis[x.v])
            dis[x.v] = dis[x.u] + x.w;

    for(int i=0;i<n;i++){
        if(dis[i] != dis2[i]){
            printf("Negative weighted cycle detected!\n");
            break;
        }
    }
    printf("%d\n",dis[n-1]);
    return 0;
}
/*
5 5
0 1 99
1 2 15
2 1 -42
2 3 10
0 4 -99
*/