#include <algorithm>
#include <iostream>
#include <list>
#include <queue>
#include <vector>

using namespace std;

struct AdjacentVertex {
  int vert_idx;
  int edge_c;
};

int main() {
  int n, m;
  cin >> n >> m;

  vector<list<AdjacentVertex>> graph(n);

  for (int i = 0; i < m; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    AdjacentVertex av;
    av.edge_c = c;
    av.vert_idx = v - 1;
    graph[u - 1].push_back(av);
    av.vert_idx = u - 1;
    graph[v - 1].push_back(av);
  }

  vector<int> vert_vals(n);  // 頂点に書き込まれた整数
  vert_vals[0] = 1;

  queue<int> q;
  q.push(0);

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (const auto &av : graph[u]) {
      const int v = av.vert_idx;
      if (0 == vert_vals[v]) {
        int vert_val_u = vert_vals[u];
        vert_vals[v] = vert_val_u == av.edge_c ? 1 + vert_val_u % n : av.edge_c;
        q.push(v);
      }
    }
  }

  if (find(vert_vals.cbegin(), vert_vals.cend(), 0) == vert_vals.cend()) {
    for (int val : vert_vals) {
      cout << val << endl;
    }
  } else {
    cout << "No" << endl;
  }

  return 0;
}
#include <bits/stdc++.h>
 
using namespace std;

const int MOD=1e9+7;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	
	int n,m;
	cin>>n>>m;
	
	vector<pair<int,int>> vp(m);
	
	map<int,int> lj;
	map<int,map<int,int>> ed;
	
	for(auto &p:vp){
		int i,j;
		cin>>i>>j;
		p={i,j};
		lj[j-1]=0;
		lj[j]=0;
		lj[j+1]=0;
		ed[0][j-1]=0;
		ed[0][j]=0;
		ed[0][j+1]=0;		
	}
	lj[n]=0;
	ed[0][n]=1;
	sort(vp.begin(),vp.end());
	queue<pair<int,int>> del;
	for(auto p:vp){
		int i=p.first, j=p.second;
		while(del.size() && del.front().first<i){
			lj[del.front().second]=del.front().first;
			del.pop();
		}
		int ijm=lj[j-1], ijp=lj[j+1];
		ed[i][j] = ed[ijm][j-1] || ed[ijp][j+1];
		del.push({i,j});
	}
	
	while(del.size()){
		lj[del.front().second]=del.front().first;
		del.pop();
	}
	int ans=0;
	for(auto p:lj){
		int j=p.first, i=p.second;
		ans+=ed[i][j];
	}
	cout<<ans;
	
    
    return 0;
}