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

#define ll long long
#define all(x) x.begin(), x.end()

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	vector<array<int, 2>> black(m);
	for(auto &[x, y] : black) cin >> x >> y;
	set<int> white;
	white.insert(n);
	sort(all(black));
	for(int i = 0; i < m;){
		int cur = black[i][0];
		vector<int> rem, ins;
		while(i < m && cur == black[i][0]){
			int l = white.count(black[i][1] - 1), r = white.count(black[i][1] + 1);
			if(l + r == 0) rem.push_back(black[i][1]);
			else ins.push_back(black[i][1]);
			++i;
		}
		for(auto j : ins) white.insert(j);
		for(auto j : rem) white.erase(j); 
	}
	cout << (int)white.size() << "\n";
}

#include<bits/stdc++.h>
using namespace std;
vector< pair< int , int > > s[2003];
int q[2000006];
int main(){
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v,w;cin>>u>>v>>w;
		s[u].push_back(make_pair(v,w));
	}
	for(int i=1;i<=n;++i){
		int h=0,t=0;
		int d[2003];memset(d,0x3f3f3f3f,sizeof(d));
		bool v[2003]={0};
		for(int j=0;j<s[i].size();++j){
			d[s[i][j].first]=min(d[s[i][j].first],s[i][j].second);
			if(!v[s[i][j].first]){
			q[++t]=s[i][j].first;
			v[q[t]]=1;}
		}
		while(++h<=t){
			v[q[h]]=0;
			for(int j=0;j<s[q[h]].size();++j)
			if(d[s[q[h]][j].first]>d[q[h]]+s[q[h]][j].second){
				d[s[q[h]][j].first]=d[q[h]]+s[q[h]][j].second;
				if(!v[s[q[h]][j].first]){
					q[++t]=s[q[h]][j].first;
					v[q[t]]=1;
				}
			}
		}
		if(d[i]!=d[0])	cout<<d[i]<<endl;
		else			cout<<"-1\n";
	}
}