Problem Statement

There are N people standing on the x-axis. Let the coordinate of Person i be x_i. For every i, x_i is an integer between 0 and 10⁹ (inclusive). It is possible that more than one person is standing at the same coordinate.

You will given M pieces of information regarding the positions of these people. The i-th piece of information has the form (L_i,R_i,D_i). This means that Person R_i is to the right of Person L_i by D_i units of distance, that is, x_Ri−x_Li=D_i holds.

It turns out that some of these M pieces of information may be incorrect. Determine if there exists a set of values (x₁,x₂,…,x_N) that is consistent with the given pieces of information.

Constraints

• 1≤N≤100 000
• 0≤M≤200 000
• 1≤L_i,R_i≤N (1≤i≤M)
• 0≤D_i≤10 000 (1≤i≤M)
• L_i≠R_i (1≤i≤M)
• If i≠j, then (L_i,R_i)≠(L_j,R_j) and (L_i,R_i)≠(R_j,L_j).
• D_i are integers.

---

Input

Input is given from Standard Input in the following format:

N ML1 R1 D1L2 R2 D2:LM RM DM

Output

If there exists a set of values (x₁,x₂,…,x_N) that is consistent with all given pieces of information, print Yes; if it does not exist, print No.

---

Sample Input 1

Copy

3 31 2 12 3 11 3 2

Sample Output 1

Copy

Yes

Some possible sets of values (x₁,x₂,x₃) are (0,1,2) and (101,102,103).

---

Sample Input 2

Copy

3 31 2 12 3 11 3 5

Sample Output 2

Copy

No

If the first two pieces of information are correct, x₃−x₁=2 holds, which is contradictory to the last piece of information.

---

Sample Input 3

Copy

4 32 1 12 3 53 4 2

Sample Output 3

Copy

Yes

---

Sample Input 4

Copy

10 38 7 1007 9 1009 8 100

Sample Output 4

Copy

No

---

Sample Input 5

Copy

100 0

Sample Output 5

Copy

Yes 题意：给定有N个人，M条信息。每条信息：L，R，D，表示第R个人在第L个人的右边距离为D。求根据这M条信息判断安排是否成立。 题解：本来以为可以在线一条一条输入输入信息的同时判断是否合法，好像是不可以。答案说是构成图，然后DFS每一个节点。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int maxn = 1e5 + 100; 8 typedef long long ll; 9 vector
           
            
              > e[maxn];10 ll dis[maxn];11 bool vis[maxn];12 int n, m,flag=0;13 14 void dfs(int x)15 {16 vis[x] = 1;17 for (int i = 0; i < e[x].size(); i++)18 {19 pair
             
               cur=e[x][i];20 if (vis[cur.first]) {21 if (dis[cur.first] - dis[x] != cur.second) {22 flag = 1; break;23 }24 }25 else {26 dis[cur.first] = dis[x] + cur.second;27 dfs(cur.first);28 }29 }30 }31 32 int main()33 {34 cin >> n >> m;35 memset(vis, 0, sizeof(vis));36 for (int i = 0; i < m; i++) {37 int l, r, d;38 cin >> l >> r >> d;39 e[l].push_back({ r,d });40 e[r].push_back({ l,-d });41 }42 flag = 0;43 for (int i = 0; i