Pink-Floyd

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <random>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

int SQR(int x) {return x * x;}
int SQRT(int n) {int l = 0, r = n + 1; while (r - l > 1) {int m = (l + r) / 2; if (m * m <= n) {l = m; } else {r = m;}} return l; }
int POW(int x, int p) {int ans = 1; while (p-->0) {ans *= x; }return ans; }
int CEIL(int x, int d) {return (x + d - 1) / d;}
int MODD(int x, int md) {return (x + md) % md; }
int GCD(int a, int b) {while (a) {b %= a; swap(a, b); } return b; }
ld LOG(int base, int x) {return log2(x) / log2(base); }

mt19937 rnd(1);

const int MINF = -1e9;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> G(n, vector<int>(n, MINF));
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        a--;
        b--;
        G[a][b] = w;
    }
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (G[i][k] > MINF && G[k][j] > MINF) {
                    G[i][j] = max(G[i][j], G[i][k] + G[k][j]);
                }
            }
        }
    }
    vector<vector<int>> Gn = G;
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (Gn[i][k] > MINF && Gn[k][j] > MINF) {
                    Gn[i][j] = max(Gn[i][j], Gn[i][k] + Gn[k][j]);
                }
            }
        }
    }
    if (Gn[0][n - 1] != G[0][n - 1]) {
        cout << ":)";
        return;
    }
    if (G[0][n - 1] == MINF) {
        cout << ":(";
        return;
    }
    cout << G[0][n - 1];
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    // cin >> t;
    while (t-->0) {
        solve();
    }
    return 0;
}