using System; using System.Collections.Generic; using System.Linq; using System.IO; using System.Runtime.CompilerServices; using System.Text; using System.Diagnostics; using System.Numerics; using static System.Console; using static System.Convert; using static System.Math; using static Template; using Pi = Pair; class Solver { public void Solve(Scanner sc) { int N, M; sc.Make(out N, out M); var uf = new UnionFind(N); var edge = Create(N, () => new List()); for (int i = 0; i < M; i++) { int a, b, c; sc.Make(out a, out b, out c); a--; b--; if (c == 1 && !uf.Union(a, b)) Fail("Yes"); if (c == 2) edge[a].Add(b); } var l = new List(); for (int i = 0; i < N; i++) { l.Add(uf[i]); } var scc = new StronglyConnectedComponents(uf.GroupCount); var ct = Create(uf.GroupCount, () => new List()); var d = Compression(l); for (int i = 0; i < N; i++) ct[d[uf[i]]].Add(i); foreach (var list in ct) { var cp = Compression(list); var st = new StronglyConnectedComponents(list.Count); foreach (var i in list) { foreach (var e in edge[i]) if (uf[i] == uf[e]) { st.AddEdge(cp[i], cp[e]); } } var p = st.Execute(); if (p.Any(v => v.Count > 1)) Fail("Yes"); } var use = Create(uf.GroupCount, () => new HashSet()); for (int i = 0; i < N; i++) foreach (var e in edge[i]) if (uf[e] != uf[i]) { if (use[d[uf[i]]].Contains(d[uf[e]])) continue; scc.AddEdge(d[uf[i]], d[uf[e]]); use[d[uf[i]]].Add(d[uf[e]]); } else Fail("Yes"); var s = scc.Execute(); if (s.All(v => v.Count == 1)) Fail("No"); else WriteLine("Yes"); } public static Dictionary Compression(IList A, int d = 0, Comparison cmp = null) { cmp = cmp ?? Comparer.Default.Compare; var dic = new Dictionary(); var cp = A.ToArray(); Array.Sort(cp, (a, b) => cmp(a, b)); for (var i = 0; i < cp.Length; i++) if (!dic.ContainsKey(cp[i])) dic[cp[i]] = d++; return dic; } } public class UnionFind { public int GroupCount { get; private set; } protected int[] data; public virtual int this[int i] => Find(i); public UnionFind(int size) { data = Create(size, () => -1); GroupCount = size; } protected int Find(int i) => data[i] < 0 ? i : (data[i] = Find(data[i])); public int Size(int i) => -data[Find(i)]; public virtual bool Union(int u, int v) { u = Find(u); v = Find(v); if (u == v) return false; if (data[u] > data[v]) swap(ref u, ref v); GroupCount--; data[u] += data[v]; data[v] = u; return true; } } public class StronglyConnectedComponents { private List[] g, rev; private Stack st; private List> scc; private int[] group; private bool[] use; public int Count { get; private set; } public int this[int i] { get { return group[i]; } } public List KthGroup(int k) => scc[k]; public StronglyConnectedComponents(int count) { g = Create(count, () => new List()); rev = Create(count, () => new List()); group = new int[count]; } public void AddEdge(int from, int to) { g[from].Add(to); rev[to].Add(from); } /// /// O(V+E) /// /// scc[i]:i番目の強連結成分の頂点 public List> Execute() { scc = new List>(); use = new bool[g.Length]; st = new Stack(); for (var i = 0; i < g.Length; i++) if (!use[i]) dfs1(i); use = new bool[g.Length]; while (st.Any()) { scc.Add(new List()); Count++; dfs2(st.Pop()); while (st.Any() && use[st.Peek()]) st.Pop(); } return scc; } private void dfs1(int index) { use[index] = true; foreach (var e in g[index]) if (!use[e]) dfs1(e); st.Push(index); } private void dfs2(int index) { group[index] = Count - 1; use[index] = true; scc[scc.Count - 1].Add(index); foreach (var e in rev[index]) if (!use[e]) dfs2(e); } } #region Template public static class Template { static void Main(string[] args) { Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); new Solver().Solve(new Scanner()); Console.Out.Flush(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool chmin(ref T a, T b) where T : IComparable { if (a.CompareTo(b) == 1) { a = b; return true; } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool chmax(ref T a, T b) where T : IComparable { if (a.CompareTo(b) == -1) { a = b; return true; } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void swap(ref T a, ref T b) { var t = b; b = a; a = t; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static void swap(this IList A, int i, int j) { var t = A[i]; A[i] = A[j]; A[j] = t; } public static T[] Create(int n, Func f) { var rt = new T[n]; for (var i = 0; i < rt.Length; ++i) rt[i] = f(); return rt; } public static T[] Create(int n, Func f) { var rt = new T[n]; for (var i = 0; i < rt.Length; ++i) rt[i] = f(i); return rt; } public static IEnumerable Shuffle(this IEnumerable A) => A.OrderBy(v => Guid.NewGuid()); public static int CompareTo(this T[] A, T[] B, Comparison cmp = null) { cmp = cmp ?? Comparer.Default.Compare; for (var i = 0; i < Min(A.Length, B.Length); i++) { int c = cmp(A[i], B[i]); if (c > 0) return 1; else if (c < 0) return -1; } if (A.Length == B.Length) return 0; if (A.Length > B.Length) return 1; else return -1; } public static int MaxElement(this IList A, Comparison cmp = null) { cmp = cmp ?? Comparer.Default.Compare; T max = A[0]; int rt = 0; for (int i = 1; i < A.Count; i++) if (cmp(max, A[i]) < 0) { max = A[i]; rt = i; } return rt; } public static T PopBack(this List A) { var v = A[A.Count - 1]; A.RemoveAt(A.Count - 1); return v; } public static void Fail(T s) { Console.WriteLine(s); Console.Out.Close(); Environment.Exit(0); } } public class Scanner { public string Str => Console.ReadLine().Trim(); public int Int => int.Parse(Str); public long Long => long.Parse(Str); public double Double => double.Parse(Str); public int[] ArrInt => Str.Split(' ').Select(int.Parse).ToArray(); public long[] ArrLong => Str.Split(' ').Select(long.Parse).ToArray(); public char[][] Grid(int n) => Create(n, () => Str.ToCharArray()); public int[] ArrInt1D(int n) => Create(n, () => Int); public long[] ArrLong1D(int n) => Create(n, () => Long); public int[][] ArrInt2D(int n) => Create(n, () => ArrInt); public long[][] ArrLong2D(int n) => Create(n, () => ArrLong); private Queue q = new Queue(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public T Next() { if (q.Count == 0) foreach (var item in Str.Split(' ')) q.Enqueue(item); return (T)Convert.ChangeType(q.Dequeue(), typeof(T)); } public void Make(out T1 v1) => v1 = Next(); public void Make(out T1 v1, out T2 v2) { v1 = Next(); v2 = Next(); } public void Make(out T1 v1, out T2 v2, out T3 v3) { Make(out v1, out v2); v3 = Next(); } public void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4) { Make(out v1, out v2, out v3); v4 = Next(); } public void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5) { Make(out v1, out v2, out v3, out v4); v5 = Next(); } public void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5, out T6 v6) { Make(out v1, out v2, out v3, out v4, out v5); v6 = Next(); } //public (T1, T2) Make() { Make(out T1 v1, out T2 v2); return (v1, v2); } //public (T1, T2, T3) Make() { Make(out T1 v1, out T2 v2, out T3 v3); return (v1, v2, v3); } //public (T1, T2, T3, T4) Make() { Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4); return (v1, v2, v3, v4); } } public class Pair : IComparable> { public T1 v1; public T2 v2; public Pair() { } public Pair(T1 v1, T2 v2) { this.v1 = v1; this.v2 = v2; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public int CompareTo(Pair p) { var c = Comparer.Default.Compare(v1, p.v1); if (c == 0) c = Comparer.Default.Compare(v2, p.v2); return c; } public override string ToString() => $"{v1.ToString()} {v2.ToString()}"; public void Deconstruct(out T1 a, out T2 b) { a = v1; b = v2; } } public class Pair : Pair, IComparable> { public T3 v3; public Pair() : base() { } public Pair(T1 v1, T2 v2, T3 v3) : base(v1, v2) { this.v3 = v3; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public int CompareTo(Pair p) { var c = base.CompareTo(p); if (c == 0) c = Comparer.Default.Compare(v3, p.v3); return c; } public override string ToString() => $"{base.ToString()} {v3.ToString()}"; public void Deconstruct(out T1 a, out T2 b, out T3 c) { Deconstruct(out a, out b); c = v3; } } #endregion