/*
一道蛮简单的差分约束的感觉OTZ
然而有很多细节和技巧可以学习
首先我们要先了解一下差分约束然后再来做这题
我们可以考虑如果输入a,b,w w==1    那么a到b连一条权值1的边
w==-1 y到x连一条权值1的边
w==0  则两个点连一条权值0的无向边就好了
那么我们建立好了这个差分系统时
我们就可以跑一边最长路了
因为是最长路所以d[]初始化要是负无穷大
和最短路一样但是是对立的
如果有一个正权环    那么我们肯定可以沿着这条正权环绕啊绕得到更长的最长路
所以不存在正确的k时就是不存在最长路的情况
即比如a到b权1(a比b大)  b到c权1(b比c大)
而c到a也权1(c比a大)   自然是无解的
所以我们就跑SPFA最长路+判负环就好了
然后就是我们可以看到
SPFA是求单源最短路径
而这道题并没有明确的起点终点
所以要得到每个点的d[]取最大值了
那么我们怎么做到呢？
这里有一个小技巧了
我们设置一个虚的源点0
然后再从0到每个顶点连一条权值为0的有向边
这样就可以求出这个所有的d[]的最大值了
OTZ被坑了很久一直过不了自己的数据包
想了半天
长见识了
然后一开始写的是STL队列   后来换成了手写循环队列练习一下Orz
窝好弱啊
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=1050;
const int MAXV=20005;
const int INF=0x7ffffff;
struct Edge
{
    int to,w,next;
    Edge()
    {
        to=next=w=-1;
    }
}e[MAXV];
int first[MAXN];
int cnt[MAXN];
int d[MAXN];
int q[MAXN];
bool in[MAXN];
int front,rear;
int n,m;
int tot;
int ans;

void inline Add_Edge(int x,int y,int w)
{
    tot++;
    e[tot].to=y;
    e[tot].w=w;
    e[tot].next=first[x];
    first[x]=tot;
}

void init()
{
    memset(first,-1,sizeof(first));
    int x,y,w;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>w;
        if(w==1)
            Add_Edge(x,y,1);
        else    if(w==-1)
            Add_Edge(y,x,1);
        else    if(w==0)
            Add_Edge(x,y,0),
            Add_Edge(y,x,0);
    }
    for(int i=1;i<=n;i++)//设一个虚源点0作为SPFA起点
        Add_Edge(0,i,0);
}

void SPFA(int s)
{
    for(int i=1;i<=n;i++)
        d[i]=-INF;
    d[s]=0;
    q[rear++]=s;
    in[s]=1;
    cnt[s]++;
    while(front!=rear)
    {
        int x=q[front];
        front=(front+1)%1005;   
        in[x]=0;
        for(int i=first[x];i!=-1;i=e[i].next)
        {
            int u=e[i].to;  int w=e[i].w;
            if(d[u]<d[x]+w)//最长路
            {
                d[u]=d[x]+w;
                if(!in[u])
                {
                    q[rear]=u;
                    rear=(rear+1)%1005;
                    in[u]=1;
                    if(++cnt[u]>n)
                    {
                        cout<<"NO"<<endl;
                        exit(0);
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,d[i]);
    cout<<ans<<endl;
}

int main()
{
    init();
    SPFA(0);
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    const ll oo_min=0xcfcfcfcfcfcfcfcf,oo_max=0x3f3f3f3f3f3f3f3f;
    
    ll n,m;
    vector<ll> a,b,c,vis,cnt,dist;
    vector<vector<ll>> e,l;
    deque<ll> q;
    
    void bfs_resize(ll size)
    {
        vis.resize(size,0),cnt.resize(size,0);
        dist.resize(size,oo_min);
        e.resize(size),l.resize(size);
        for (ll i=0;i<size;i++)
            e[i].clear(),l[i].clear();
        q.clear();
    }
    void add_edge(ll x,ll y,ll d)
    {
        e[x].push_back(y);
        l[x].push_back(d);
    }
    ll bfs()
    {
        dist[0]=0;
        for (vis[0]=1,cnt[0]++,q.push_back(0);!q.empty();vis[q.front()]=0,q.pop_front())
        {
            ll now=q.front();
            for (ll i=0;i<e[now].size();i++)
                if (dist[now]+l[now][i]>dist[e[now][i]])
                {
                    dist[e[now][i]]=dist[now]+l[now][i];
                    if (vis[e[now][i]]==0)
                    {
                        if (cnt[e[now][i]]>=n)
                            return -1;
                        else
                        {
                            vis[e[now][i]]=1,cnt[e[now][i]]++;
                            q.push_back(e[now][i]);
                        }
                    }
                    else if (now==e[now][i])
                        return -1;
                }
        }
        ll ans=-1;
        for (ll i=1;i<=n;i++)
            ans=max(ans,dist[i]);
        return ans;
    }
    void main()
    {
        scanf("%lld%lld",&n,&m);
        a.resize(m,0),b.resize(m,0),c.resize(m,0);
        for (ll i=0;i<m;i++)
            scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
        bfs_resize(n+1);
        for (ll i=1;i<=n;i++)
            add_edge(0,i,0);
        for (ll i=0;i<m;i++)
            if (c[i]==-1)
                add_edge(a[i],b[i],1);
            else if (c[i]==1)
                add_edge(b[i],a[i],1);
            else if (c[i]==0)
                add_edge(a[i],b[i],0),add_edge(b[i],a[i],0);
        ll ans=bfs();
        if (ans==-1)
            printf("NO\n");
        else
            printf("%lld\n",ans);
    }
}

int main()
{
    dts::main();
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define N 1001
#define next nextt
using namespace std;
int n,m,fa[N],val[N],deg[N],s[N*100],t[N*100],tot=0;
int ce[N],to[N*200],next[N*200],cnt=0,ans=0;
int find(int v){//并查集缩点 
    return fa[v]==v?v:fa[v]=find(fa[v]);
}
void turbo(){//拓扑差分 
    int i,qu[N*2],l=1,len=0,p,v;
    for(i=1;i<=n;i++){
        if(deg[i]==0){
            val[i]=0;
            qu[++len]=i;
        }
    }
    while(l<=len){
        v=qu[l];
        l++;
        for(p=ce[v];p;p=next[p]){
            deg[to[p]]--;
            if(deg[to[p]]==0){
                qu[++len]=to[p];
                val[to[p]]=val[v]+1;
                ans=max(ans,val[to[p]]);
            }
        }
    }
}
int main(){
    int i,a,b,k;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        fa[i]=i;
        deg[i]=ce[i]=0;
    }
    for(i=1;i<=m;i++){
        cin>>a>>b>>k;
        if(k==-1){
            s[++tot]=a;
            t[tot]=b;
        }
        if(k==1){
            s[++tot]=b;
            t[tot]=a;
        }
        if(k==0){
            a=find(a);
            b=find(b);
            if(a!=b) fa[a]=b;
        }
    }
    for(i=1;i<=tot;i++){
        a=find(s[i]);
        b=find(t[i]);
        to[++cnt]=b;
        deg[b]++;
        next[cnt]=ce[a];
        ce[a]=cnt;
    }
    turbo();
    for(i=1;i<=n;i++){
        if(deg[i]){
            cout<<"NO";
            return 0;
        }
    }
    cout<<ans;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7654321;
const double PI=3.1415926;
const double eps=1e-8;

int n,m;
int fa[1001];
vector<int> g[1001],g2[1001],re[1001];
bool a[1001][1001];
int bel[1001];
int out[1001];
int cnt;
int ans;
int tot;
struct node {
    int id,v;
};
queue<node> q;
int find(int x) {
    return (x==fa[x])?x:(fa[x]=find(fa[x]));
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    FOR(i,n) fa[i]=i;
    FOR(i,m) {
        int x,y,z;
        cin>>x>>y>>z;
        if (z==0) {
            int u=find(x),v=find(y);
            if (u!=v) fa[u]=v;
        } else if (z==1) {
            g2[x].pb(y);
        } else {
            g2[y].pb(x);
        }
    }
    FOR(i,n) {
        if (bel[find(i)]==0) {
            bel[find(i)]=++cnt;
        }
    }
    //FOR(i,n) cout<<bel[i]<<endl;
    FOR(i,n) {
        int t=bel[find(i)];
        for (int j=0;j<g2[i].size();j++) {
            int x=g2[i][j];
            int t2=bel[find(x)];
            if (t==t2) {
                cout<<"NO"<<endl;
                return 0;
            }
            if (!a[t][t2]) {
                a[t][t2]=1;
                g[t].pb(t2);
                re[t2].pb(t);
                ++out[t];
            }
        }
    }
    /*
    cout<<cnt<<endl;
    FOR(i,cnt) {
        for (int j=0;j<g[i].size();j++) cout<<g[i][j]<<" ";
        cout<<endl;
    }*/
    FOR(i,cnt) if (!out[i]) {
        ++tot;
        q.push(node{i,0});
    }
    while (q.size()) {
        node x=q.front();q.pop();
        for (int i=0;i<re[x.id].size();i++) {
            int to=re[x.id][i];
            if (--out[to]==0) {
                q.push(node{to,x.v+1});
                ++tot;
                ans=max(ans,x.v+1);
            }
        }
    }
    if (tot!=cnt) {
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<ans<<endl;
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
#include <tuple>

using namespace std;

const int maxN = 1000 + 5;
const int maxM = 10000 + 5;
const int inf = 0x3f3f3f3f;

//first: to
//second: len
vector<pair<int, int>> elist[maxN];
//int inDeg[maxN] = {0};
bool inStack[maxN] = {false};
int dist[maxN];
int N, M;

void input()
{
    auto addEdge = [] (int f, int t, int d) -> void {
        elist[f].emplace_back(t, d);
        //inDeg[t] += 1;
    };

    scanf("%d%d", &N, &M);
    for (int u, v, f, i = 0; i < M; i++)
    {
        scanf("%d%d%d", &u, &v, &f);
        switch (f)
        {
        case -1:
            addEdge(v, u, -1);
            break;
        case 0:
            addEdge(u, v, 0);
            addEdge(v, u, 0);
            break;
        case 1:
            addEdge(u, v, -1);
            break;
        default:
            break;
        }
    }

    for (int i = 1; i <= N; i++)
        addEdge(0, i, 0);
}

void initDfs()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 0;
}

bool dfs(int cur)
{
    inStack[cur] = true;

    int to, len;
    for (auto& pr: elist[cur])
    {
        tie(to, len) = pr;
        if (dist[cur] + len >= dist[to])
            continue;
        dist[to] = dist[cur] + len;
        if (inStack[to] || !dfs(to))
            return false;
    }

    inStack[cur] = false;
    return true;
}

void solve()
{
    initDfs();
    if (!dfs(0))
    {
        printf("NO");
        return;
    }
    printf("%d", -*min_element(dist + 1, dist + N + 1));
}

int main()
{
    input();
    solve();
    return 0;
}