форд бэлман отриц-й цикл OK

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
#define vec vector
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvl(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}


void cvv(vector <vector <int> > &v){
    for (auto x: v) cv(x);
    cout<<"\n";
}
int n,m;
struct ed{
    int fr, to, w;
};
vector <ed> G;
const ll inf = 1e18;
vector <ll> dst;
vector <ll> check;
void frd(){
    dst.resize(n, -inf);
    dst[0] = 0;
    for (int l = 0; l < n-1; ++l){
        // cout<<"l = "<<l<<"\n";
        for (int i = 0; i < m; ++i){
            if (dst[G[i].fr] == -inf) continue;
            if (dst[G[i].to] < dst[G[i].fr] + G[i].w){
                dst[G[i].to] =  dst[G[i].fr] + G[i].w;
            }
        }
    }
}

vector <vector <bool> > can;//попасть из i в j

const int wh = 900, gr = 678, bl = 999;


vector <bool> here;
vector <int> clr;
vector <vector<int>> goG;
void dfs(int v){
    clr[v] = gr;
    here[v] = 1;
    for (int u: goG[v]){
        if (clr[u] == wh){
            dfs(u);
        }
    }
    clr[v] = bl;
}


void connect(){
    for (int i = 0; i < n; ++i){
        clr.assign(n, wh);
        here.assign(n, 0);
        dfs(i);
        can.push_back(here);
    }
}
void cvb(vector <bool> v){
    for (bool x: v) cout<<x<<' ';
    cout<<"\n";
}

void shCan(){
    cout<<"can\n";
    for (int i=0;i<n;++i){
        cout<<i+1<<" : ";
         cvb(can[i]);

    }cout<<"\n";
}

void chk(){
    if (dst[n-1] == -inf){
        cout<<":(\n";
        exit(0);
    }
    connect();
    check = dst;
    for (int l = 0; l < n-1; ++l){
        // cout<<"l = "<<l<<"\n";
        for (int i = 0; i < m; ++i){
            if (check[G[i].fr] == -inf) continue;
            if (check[G[i].to] < check[G[i].fr] + G[i].w){
                check[G[i].to] =  check[G[i].fr] + G[i].w;
            }
        }
    }
    //cout<<"dst check\n";
    //cvl(dst); cvl(check);
    /*if (check[n-1] > dst[n-1]){
        cout<<":)\n";
        exit(0);
    }*/
    //shCan();
    for (int i=0;i<n;++i){
        if (dst[i] > -inf && can[i][n-1] == 1 && check[i] > dst[i]){
            cout<<":)\n";
            exit(0);
        }
    }
}





void shG(){
    for (int i=0;i<m;++i){
        cout<<G[i].fr+1<<' '<<G[i].to+1<<' '<<G[i].w<<"\n";
    }
}







int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	G.resize(m);
	goG.resize(n);
	for (int i = 0; i < m;++i) {
        cin>>G[i].fr>>G[i].to>>G[i].w;
        G[i].fr--;
        G[i].to--;
        goG[G[i].fr].push_back(G[i].to);
	}
	//shG();
	frd();
	chk();
	cout<<dst[n-1]<<"\n";
	//cout<<dst[n-1]<<"\n";
}
/*
2 2
1 2 3
1 2 7

5 6
1 5 1
1 2 -10000
3 2 2
2 4 0
4 3 -1
2 1 -10000
*/