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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.nio.CharBuffer;
import java.io.IOException;
import java.nio.charset.CharsetDecoder;
import java.util.OptionalInt;
import java.nio.charset.StandardCharsets;
import java.nio.ByteBuffer;
import java.io.UncheckedIOException;
import java.util.Objects;
import java.nio.charset.Charset;
import java.io.Writer;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner2 in = new LightScanner2(inputStream);
        LightWriter2 out = new LightWriter2(outputStream);
        ECapitalism solver = new ECapitalism();
        solver.solve(1, in, out);
        out.close();
    }

    static class ECapitalism {
        private static final int INF = 1000_000_000;

        public void solve(int testNumber, LightScanner2 in, LightWriter2 out) {
            out.setBoolLabel(LightWriter2.BoolLabel.YES_NO_ALL_UP);
            int n = in.ints(), m = in.ints();
        /*
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) nodes[i] = new Node(i);
        IntWeightedUnionFind wuf = new IntWeightedUnionFind(n);
        BellmanFord bf = new BellmanFord(n);
         */
            int[] xs = new int[m], ys = new int[m];
            boolean[] force = new boolean[m];
            int[][] dist = new int[n][n];
            ArrayUtil.fill(dist, INF);
            for (int i = 0; i < n; i++) dist[i][i] = 0;

            for (int i = 0; i < m; i++) {
                xs[i] = in.ints() - 1;
                ys[i] = in.ints() - 1;
                force[i] = in.ints() == 1;
                if (force[i]) {
                    dist[xs[i]][ys[i]] = 1;
                    dist[ys[i]][xs[i]] = -1;
                /*
                if (!wuf.union(xs[i], ys[i], 1)) {
                    out.noln();
                    return;
                }*/
                } else {
                    dist[xs[i]][ys[i]] = 1;
                    dist[ys[i]][xs[i]] = 1;
                /*
                nodes[xs[i]].adjs.add(nodes[ys[i]]);
                nodes[ys[i]].adjs.add(nodes[xs[i]]);
                bf.addEdge(xs[i], ys[i], 1);
                bf.addEdge(ys[i], xs[i], 1);*/
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);
                    }
                }
            }

        /*
        List<List<Node>> groups = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            groups.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            nodes[i].grid = wuf.find(i);
            nodes[i].sameGroup = groups.get(nodes[i].grid);
            nodes[i].sameGroup.add(nodes[i]);
            nodes[i].potential = (int) wuf.getWeight(i);
        }
        //System.out.println(Arrays.toString(nodes));

        for (int i = 0; i < m; i++) {
            if (!force[i]) continue;
            bf.addEdge(xs[i], ys[i], 1);
            bf.addEdge(ys[i], xs[i], -1);
        }
         */

            long ineq = -1;
            int[] ans = null;
            loop:
            for (int s = 0; s < n; s++) {
                for (int i = 0; i < m; i++) {
                    if (Math.abs(dist[s][xs[i]] - dist[s][ys[i]]) != 1) continue loop;
                    if (force[i] && dist[s][ys[i]] - dist[s][xs[i]] != 1) continue loop;
                }
                long max = IntMath.max(dist[s]) - IntMath.min(dist[s]);
                if (max > ineq) {
                    ans = dist[s];
                    ineq = max;
                }
            }

            if (ans == null) {
                out.noln();
            } else {
                long min = IntMath.min(ans);
                out.yesln().ans(ineq).ln();
                for (int i = 0; i < n; i++) out.ans(ans[i] - min);
                out.ln();
            }
        }

    }

    static class LightWriter2 implements AutoCloseable {
        private static final int BUF_SIZE = 16 * 1024;
        private static final int BUF_THRESHOLD = 1024;
        private final OutputStream out;
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private boolean autoflush = false;
        private boolean breaked = true;
        private LightWriter2.BoolLabel boolLabel = LightWriter2.BoolLabel.YES_NO_FIRST_UP;

        public LightWriter2(OutputStream out) {
            this.out = out;
        }

        public LightWriter2(Writer out) {
            this.out = new LightWriter2.WriterOutputStream(out);
        }

        public void setBoolLabel(LightWriter2.BoolLabel label) {
            this.boolLabel = Objects.requireNonNull(label);
        }

        private void allocate(int n) {
            if (ptr + n <= BUF_SIZE) return;
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            if (BUF_SIZE < n) throw new IllegalArgumentException("Internal buffer exceeded");
        }

        public void close() {
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
                out.flush();
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        public LightWriter2 print(char c) {
            allocate(1);
            buf[ptr++] = (byte) c;
            breaked = false;
            return this;
        }

        public LightWriter2 print(String s) {
            byte[] bytes = s.getBytes();
            int n = bytes.length;
            if (n <= BUF_THRESHOLD) {
                allocate(n);
                System.arraycopy(bytes, 0, buf, ptr, n);
                ptr += n;
                return this;
            }
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
                out.write(bytes);
                out.flush();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter2 ans(String s) {
            if (!breaked) print(' ');
            breaked = false;
            return print(s);
        }

        private static int countDigits(long l) {
            if (l >= 1000000000000000000L) return 19;
            if (l >= 100000000000000000L) return 18;
            if (l >= 10000000000000000L) return 17;
            if (l >= 1000000000000000L) return 16;
            if (l >= 100000000000000L) return 15;
            if (l >= 10000000000000L) return 14;
            if (l >= 1000000000000L) return 13;
            if (l >= 100000000000L) return 12;
            if (l >= 10000000000L) return 11;
            if (l >= 1000000000L) return 10;
            if (l >= 100000000L) return 9;
            if (l >= 10000000L) return 8;
            if (l >= 1000000L) return 7;
            if (l >= 100000L) return 6;
            if (l >= 10000L) return 5;
            if (l >= 1000L) return 4;
            if (l >= 100L) return 3;
            if (l >= 10L) return 2;
            return 1;
        }

        public LightWriter2 ans(long x) {
            allocate(24);
            if (!breaked) buf[ptr++] = ' ';
            breaked = false;

            if (x < 0) {
                buf[ptr++] = '-';
                x = -x;
            }
            int n = countDigits(x);
            for (int i = ptr + n - 1; ptr <= i; i--) {
                buf[i] = (byte) (x % 10 + '0');
                x /= 10;
            }
            ptr += n;

            return this;
        }

        public LightWriter2 ans(boolean b) {
            return ans(boolLabel.transfer(b));
        }

        public LightWriter2 yesln() {
            return ans(true).ln();
        }

        public LightWriter2 noln() {
            return ans(false).ln();
        }

        public LightWriter2 ln() {
            allocate(1);
            buf[ptr++] = '\n';
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        public enum BoolLabel {
            YES_NO_FIRST_UP("Yes", "No"),
            YES_NO_ALL_UP("YES", "NO"),
            YES_NO_ALL_DOWN("yes", "no"),
            Y_N_ALL_UP("Y", "N"),
            POSSIBLE_IMPOSSIBLE_FIRST_UP("Possible", "Impossible"),
            POSSIBLE_IMPOSSIBLE_ALL_UP("POSSIBLE", "IMPOSSIBLE"),
            POSSIBLE_IMPOSSIBLE_ALL_DOWN("possible", "impossible"),
            FIRST_SECOND_FIRST_UP("First", "Second"),
            FIRST_SECOND_ALL_UP("FIRST", "SECOND"),
            FIRST_SECOND_ALL_DOWN("first", "second"),
            ALICE_BOB_FIRST_UP("Alice", "Bob"),
            ALICE_BOB_ALL_UP("ALICE", "BOB"),
            ALICE_BOB_ALL_DOWN("alice", "bob"),
            ;
            private final String positive;
            private final String negative;

            BoolLabel(String positive, String negative) {
                this.positive = positive;
                this.negative = negative;
            }

            private String transfer(boolean f) {
                return f ? positive : negative;
            }

        }

        private static class WriterOutputStream extends OutputStream {
            final Writer writer;
            final CharsetDecoder decoder;

            WriterOutputStream(Writer writer) {
                this.writer = writer;
                this.decoder = StandardCharsets.UTF_8.newDecoder();
            }

            public void write(int b) throws IOException {
                writer.write(b);
            }

            public void write(byte[] b) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b)).array());
            }

            public void write(byte[] b, int off, int len) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b, off, len)).array());
            }

            public void flush() throws IOException {
                writer.flush();
            }

            public void close() throws IOException {
                writer.close();
            }

        }

    }

    static abstract class LightScannerAdapter implements AutoCloseable {
        public abstract void close();

    }

    static final class IntMath {
        private IntMath() {
        }

        public static int min(int... v) {
            return Arrays.stream(v).min().orElseThrow(NoSuchElementException::new);
        }

        public static int max(int... v) {
            return Arrays.stream(v).max().orElseThrow(NoSuchElementException::new);
        }

    }

    static class LightScanner2 extends LightScannerAdapter {
        private static final int BUF_SIZE = 16 * 1024;
        private final InputStream stream;
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private int len;

        public LightScanner2(InputStream stream) {
            this.stream = stream;
        }

        private void reload() {
            try {
                ptr = 0;
                len = stream.read(buf);
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private void load(int n) {
            if (ptr + n <= len) return;
            System.arraycopy(buf, ptr, buf, 0, len - ptr);
            len -= ptr;
            ptr = 0;
            try {
                int r = stream.read(buf, len, BUF_SIZE - len);
                if (r == -1) return;
                len += r;
                if (len != BUF_SIZE) buf[len] = '\n';
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private void skip() {
            while (len != -1) {
                while (ptr < len && isTokenSeparator(buf[ptr])) ptr++;
                if (ptr < len) return;
                reload();
            }
            throw new NoSuchElementException("EOF");
        }

        public int ints() {
            skip();
            load(12);
            int b = buf[ptr++];
            boolean negate;
            if (b == '-') {
                negate = true;
                b = buf[ptr++];
            } else negate = false;
            int x = 0;
            for (; !isTokenSeparator(b); b = buf[ptr++]) {
                if ('0' <= b && b <= '9') x = x * 10 + b - '0';
                else throw new NumberFormatException("Unexpected character '" + ((char) b) + "'");
            }
            return negate ? -x : x;
        }

        public void close() {
            try {
                stream.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        private static boolean isTokenSeparator(int b) {
            return b < 33 || 126 < b;
        }

    }

    static final class ArrayUtil {
        private ArrayUtil() {
        }

        public static void fill(int[] a, int v) {
            Arrays.fill(a, v);
        }

        public static void fill(int[][] a, int v) {
            for (int i = 0; i < a.length; i++) {
                fill(a[i], v);
            }
        }

    }
}