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

#ifdef Dhiraj
    #include "D:/dhiraj/Programming/debug.h"
#else
    #define d(...) 11
    #define cerr if(0) cerr
#endif

#define ll long long int
#define endl '\n'

template <typename T, typename U>
inline istream& operator >> (istream& in, pair<T, U>& a) {
    in >> a.first >> a.second;
    return in;
}
template <typename T>
inline istream& operator >> (istream& in, vector<T>& a) {
    for(auto& x : a) in >> x;
    return in;
}

void solve(int &T)
{
    ll n, m;
    cin >> n >> m;

    vector<ll> b(m + 2);
    for(ll i = 0; i < m; i++) {
        cin >> b[i + 1];
    }
    b[0] = 0;
    b[m + 1] = n + 1;

    if(m == 0) {
        cout << 1 << endl;
        return;
    }
    if(m == n) {
        cout << 0 << endl;
        return;
    }
    sort(b.begin(), b.end());

    ll mn = 1e10;
    for(ll i = 1; i < m + 2; i++)
    {
        if(b[i] != b[i - 1] + 1) {
            mn = min(mn, b[i] - b[i - 1] - 1);
        }
    }
    d(mn);

    if(mn == 1e10) {
        cout << 0 << endl;
        return;
    }

    ll ans = 0;
    for(ll i = 1; i < m + 2; i++)
    {
        if(b[i] != b[i - 1] + 1) {
            ans += (b[i] - b[i - 1] - 1 + mn - 1) / mn;
        }
    }
    cout << ans << endl;
}

int main()
{
    #ifdef Dhiraj
        freopen("D:/dhiraj/Programming/i1.txt", "r", stdin);
        freopen("D:/dhiraj/Programming/o1.txt", "w", stdout);
        // freopen("D:/dhiraj/Programming/e1.txt", "w", stderr);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(0);

    int tc = 1;
    for(int i = 1; i <= tc; i++) {
        cerr << "Case #" << i << "\n";
        solve(i);
    }
    return 0;
}
#include <bits/stdc++.h>

using namespace std;

#define closeSync ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair<int,ll> pil;
const int MAXN = 100005;
const ll MOD = 1e9+7;
const ll INF = 1e18;

vector<pil> mp[MAXN];
ll dis[MAXN];
int vis[MAXN];
ll ans[MAXN];
struct Edge{
	int u,v;
	ll w;
};
struct E{
	int v;
	ll w;
	bool operator<(const E& x)const
	{
		return w > x.w;
	}
};
int n,m;

ll dij(int st,int ed)
{
	for (int i=1;i<=n+1;i++)
		vis[i] = 0,dis[i] = INF;
	priority_queue<E> q;
	q.push({st,0});
	dis[st] = 0;
	while (!q.empty())
	{
		E u = q.top();
		q.pop();
		if (vis[u.v])
			continue;
		vis[u.v] = 1;
		for (auto c : mp[u.v])
		{
			if (dis[u.v] + c.second < dis[c.first])
			{
				dis[c.first] = dis[u.v] + c.second;
				q.push({c.first,dis[c.first]});
			}
		}
	}
	return dis[ed];
}

inline void solve()
{
	
	cin >> n >> m;
	vector<Edge> ve;
	for (int i=1;i<=m;i++)
	{
		int u,v;ll w;
		cin >> u >> v >> w;
		ve.push_back({u,v,w});
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
			mp[j].clear(),mp[j].resize(0);
		for (auto c : ve)
		{
			if (c.v == i)
				mp[c.u].push_back({n+1,c.w});
			else 
				mp[c.u].push_back({c.v,c.w});
		}
		ll tmp = dij(i,n+1);
		ans[i] = (tmp == INF ? -1 : tmp);
	}
	for (int i=1;i<=n;i++)
		cout << ans[i] << endl;

}


int main()
{closeSync;
	// int T;
	// cin >> T;
	// while (T--)
		solve();
	return 0;
}