Problem: A society can be represented by a connected, undirected graph of n vertices and m edges. The vertices represent people, and an edge (i,j) represents a friendship between people i and j.

In society, the i-th person has an income a_i. A person i is envious of person j if a_j=a_i+1. That is if person j has exactly 1 more unit of income than person i.

The society is called capitalist if for every pair of friends one is envious of the other. For some friendships, you know which friend is envious of the other. For the remaining friendships, you do not know the direction of envy.

The income inequality of society is defined as max_{1 ≤ i ≤ n} a_i - min_{1 ≤ i ≤ n} a_i.

You only know the friendships and not the incomes. If it is impossible for this society to be capitalist with the given knowledge, you should report about it. Otherwise, you should find an assignment of incomes in which the society is capitalist, and the income inequality is maximized.

Input

The first line contains two integers n, m (1≤ n≤ 200, n-1≤ m≤ 2000) — the number of people and friendships, respectively.

The following m lines describe the friendships. Each friendship is described by three integers i, j, b (1≤ i, j≤ n, i≠ j, 0≤ b≤ 1). This denotes that people i and j are friends. If b=1, we require that person i is envious of person j. If b=0, one friend should be envious of the other in either direction.

There is at most one friendship between each pair of people. It is guaranteed that if we consider the friendships as undirected edges, the graph is connected.

Output

Print "YES" if it is possible that the society is capitalist, or "NO" otherwise. You can print characters in any case (upper or lower).

If the answer is "YES", you should print two additional lines. In the first line, print the maximum possible income inequality. On the next line you should print n integers a_1,…, a_n (0≤ a_i≤ 10^6), where a_i denotes the income of the i-th person.

We can prove that if there exists a solution, there exists one where 0≤ a_i≤ 10^6 for all i.

If there exist multiple solutions, print any.

Examples

Input


6 6
1 2 0
3 2 0
2 5 0
6 5 1
6 3 0
2 4 1


Output


YES
3
3 2 1 3 1 0 


Input


4 4
1 2 1
2 3 0
3 4 1
4 1 1


Output


NO


Input


1 0


Output


YES
0
0 

Note

In the first test, we can show that an income inequality greater than 3 is impossible for the given society. In the given answer with income inequality equal to 3:

  * Person 2 is envious of person 1. 
  * Person 3 is envious of person 2. 
  * Person 5 is envious of person 2. 
  * Person 6 is envious of person 5 (the required direction is satisfied). 
  * Person 6 is envious of person 3. 
  * Person 2 is envious of person 4 (the required direction is satisfied). 



In the second test, we can show that there is no way to assign incomes to satisfy all requirements.

Solution (in CPP):

Solution:
///////////////////////////////////////////////////////////////////////////////

#include <bits/stdc++.h>
#include <unistd.h>
#include <time.h>
#include <sys/time.h>

using namespace std;

///////////////////////////////////////////////////////////////////////////////

#define DEBUG 0

#define pb push_back
#define V vector
#define M unordered_map
#define S static

#define rep(i,n) for(ll i=0LL; i<n; ++i)
#define srep(i,s,n) for(ll i=s; i<n; ++i)
#define rrep(i,n) for(ll i=n-1LL; i>=0LL; --i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CIN(x) do { \
        assert(!cin.eof()); \
        cin >> x; \
        assert(!cin.fail()); \
} while(0);
#if DEBUG
#define debug_print(...) _debug_print(__VA_ARGS__)
#define debug_printf(...) printf(__VA_ARGS__)
#define debug_print_time _debug_print_time
#else // DEBUG
#define debug_print(...)
#define debug_printf(...)
#define debug_print_time
#endif // DEBUG

typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll, ll> t2;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;
template <typename T>
using priority_queue_incr = priority_queue<T, V<T>, greater<T> >;

///////////////////////////////////////////////////////////////////////////////

template <typename TT, typename T>
T get_m(M<TT, T> &m, TT k, T default_value)
{
    if (m.find(k) == m.end()) return m[k] = default_value;
    return m[k];
}

template <typename TT, typename T>
void incr_m(M<TT, T> &m, TT k)
{
    if (m.find(k) == m.end()) m[k] = 0;
    m[k]++;
}

template <typename TT, typename T>
void incr_m(map<TT, T> &m, TT k)
{
    if (m.find(k) == m.end()) m[k] = 0;
    m[k]++;
}

void llin(ll &a)
{
    CIN(a);
}

void llinl1(V<ll> &v, ll count)
{
    for (ll i = 0LL; i < count; ++i) {
        ll a;
        CIN(a);
        v.push_back(a);
    }
}

void llinl2(V<t2> &v, ll count)
{
    for (ll i = 0LL; i < count; ++i) {
        ll a, b;
        CIN(a >> b);
        v.push_back(t2(a, b));
    }
}

void llinl3(V<t3> &v, ll count)
{
    for (ll i = 0LL; i < count; ++i) {
        ll a, b, c;
        CIN(a >> b >> c);
        v.push_back(t3(a, b, c));
    }
}

void llinl4(V<t4> &v, ll count)
{
    for (ll i = 0LL; i < count; ++i) {
        ll a, b, c, d;
        CIN(a >> b >> c >> d);
        v.push_back(t4(a, b, c, d));
    }
}

void llina(V<ll> &v, ll count)
{
    llinl1(v, count);
}

template <typename T>
void sort(V<T> &v)
{
    sort(v.begin(), v.end());
}

template <typename T>
void sort_reverse(V<T> &v)
{
    sort(v.begin(), v.end(), greater<T>());
}

ll msec()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    ll ret = 0;
    ret += tv.tv_sec * 1000LL;
    ret += tv.tv_usec / 1000LL;
    return ret;
}


template <typename T>
void _debug_print(T x)
{
    cout << x << endl;
}

void _debug_print(const t2 &x)
{
    ll x1 = get<0>(x);
    ll x2 = get<1>(x);
    cout << "-- " << x1 << " -- " << x2 << endl;
}

void _debug_print(const t3 &x)
{
    ll x1 = get<0>(x);
    ll x2 = get<1>(x);
    ll x3 = get<2>(x);
    cout << "-- " << x1 << " -- " << x2 << " -- " << x3 << endl;
}

void _debug_print(const t4 &x)
{
    ll x1 = get<0>(x);
    ll x2 = get<1>(x);
    ll x3 = get<2>(x);
    ll x4 = get<3>(x);
    cout << "-- " << x1 << " -- " << x2
         << " -- " << x3 << " -- " << x4 << endl;
}

template <typename T>
void _debug_print(T xarray[], ll n)
{
    rep (i, n) _debug_print(xarray[i]);
}

template <typename T>
void _debug_print(const V<T> &xlist)
{
    for (auto x : xlist) {
        cout << "-- ";
        _debug_print(x);
    }
}

template <typename T>
void _debug_print(const set<T> &xset)
{
    for (auto x : xset) {
        cout << "-- ";
        _debug_print(x);
    }
}

template <typename TT, typename T>
void _debug_print(const M<TT, T> &xlist)
{
    for (auto x : xlist) {
        TT k = x.first;
        T v = x.second;
        cout << "====" << endl;
        cout << "K=";
        _debug_print(k);
        cout << "V=";
        _debug_print(v);
    }
}

template <typename TT, typename T>
void _debug_print(const map<TT, T> &xlist)
{
    for (auto x : xlist) {
        TT k = x.first;
        T v = x.second;
        cout << "====" << endl;
        cout << "K=";
        _debug_print(k);
        cout << "V=";
        _debug_print(v);
    }
}

void _debug_print_time(const char *prefix)
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
#if DEBUG
    struct tm *tm = localtime(&tv.tv_sec);
#endif
    debug_printf("-- %s %02d:%02d:%02d.%06ld\n",
                  prefix, tm->tm_hour, tm->tm_min, tm->tm_sec, tv.tv_usec);
}

///////////////////////////////////////////////////////////////////////////////

void _main();
int main()
{
    cout << setprecision(12);
#if !DEBUG
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif

    _main();
    return 0;
}

#define SZN  (210LL)
#define SZM  (2010LL)
;

bool bingraph(const V<t3> &uvblist, ll n, ll m)
{
    S V<ll> edges[SZN];
    for (auto uvb : uvblist) {
        ll u = get<0>(uvb);
        ll v = get<1>(uvb);
        edges[u].pb(v);
        edges[v].pb(u);
    }

    queue<ll> q;
    S ll groups[SZN];
    rep (i, SZN) groups[i] = -1;

    q.push(1);
    groups[1] = 0;

    while (q.size()) {
        ll v = q.front(); q.pop();
        ll g = groups[v];
        ll ng = !g;
        for (auto nv : edges[v]) {
            if (groups[nv] == ng) continue;
            if (groups[nv] < 0) {
                q.push(nv);
                groups[nv] = ng;
                continue;
            }
            return false;
        }
    }

    return true;
}

void _update(ll costs[], const V<t2> edges[], ll n, ll m)
{
    rep (xx, n+2) {
        srep (v, 1, n+1) {
            for (auto ni : edges[v]) {
                ll nc = get<0>(ni);
                ll nv = get<1>(ni);
                costs[nv] = min(costs[nv], costs[v] + nc);
            }
        }
    }
}

bool negloop(const V<t2> edges[], ll n, ll m)
{
    S ll costs[SZN];
    rep (i, SZN) costs[i] = 1e18;
    costs[1] = 0;

    _update(costs, edges, n, m);
    S ll costs2[SZN];
    memcpy(costs2, costs, sizeof(costs2));
    _update(costs, edges, n, m);

    srep (v, 1, n+1) if (costs[v] != costs2[v]) return true;
    return false;
}

void _main()
{
    ll n; llin(n);
    ll m; llin(m);
    V<t3> uvblist; llinl3(uvblist, m);

    if (!bingraph(uvblist, n, m)) {
        cout << "NO" << endl;
        return;
    }

    S V<t2> edges[SZN];
    for (auto uvb : uvblist) {
        ll u = get<0>(uvb);
        ll v = get<1>(uvb);
        ll b = get<2>(uvb);
        if (b) {
            edges[u].pb(t2(1, v));
            edges[v].pb(t2(-1, u));
        }
        else {
            edges[u].pb(t2(1, v));
            edges[v].pb(t2(1, u));
        }
    }

    if (negloop(edges, n, m)) {
        cout << "NO" << endl;
        return;
    }

    S ll d[SZN][SZN];
    rep (i, SZN) rep (j, SZN) d[i][j] = 1e18;
    rep (i, SZN) d[i][i] = 0;
    srep (v, 1, n+1) {
        for (auto ni : edges[v]) {
            ll c = get<0>(ni);
            ll nv = get<1>(ni);
            d[v][nv] = c;
        }
    }

    srep (i, 1, n+1) srep (j, 1, n+1) srep (k, 1, n+1) {
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
    }

    ll maxd = -1e18;
    ll maxu = -1;
    ll maxv = -1;
    srep (u, 1, n+1) srep (v, 1, n+1) {
        if (d[u][v] > maxd) {
            maxd = d[u][v];
            maxu = u;
            maxv = v;
        }
    }

    cout << "YES" << endl;
    cout << maxd << endl;
    srep (v, 1, n+1) cout << d[maxu][v] << " ";
    cout << endl;
}

///////////////////////////////////////////////////////////////////////////////