#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 100001;

int n, m, col[N];
vector <int> v[N];

int dfs(int node, int pnode){
    for(auto &i : v[node]){
        if(col[i] != -1){
            if(col[i] != (col[node] ^ 1)) return 1;
        }
        else{
            col[i] = col[node] ^ 1;
            int f = dfs(i, node);
            if(f == 1) return 1;
        }
    }
    return 0;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(col, -1, sizeof col);
    cin >> n >> m;
    for(int i = 0 ; i < m ; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    col[1] = 0;
    if(dfs(1, 0)) finish(1LL * n * (n - 1) / 2 - m);
    int r = 0, b = 0;
    for(int i = 1 ; i <= n ; i++){
        if(col[i] == 0) r++;
        else b++;
    }
    cout << 1LL * r * b - m << endl;
}

#include <bits/stdc++.h>
#define N 1000010
#define F first
#define S second
using namespace std;
int n,m,book[N],nd;
vector<pair<int,int> > ed[N];
vector<int> col[N],ng[N];
int main(){
	int x,y,c,i,j,k;
	//memset(book,-1,sizeof(book));
	cin>>n>>m;
	nd=n;
	for(i=0;i<m;i++)
	{
		cin>>x>>y>>c;
		x--;
		y--;
		ed[x].push_back(make_pair(c,y));
		ed[y].push_back(make_pair(c,x));
		col[c].push_back(x);
		col[c].push_back(y);
	}
	for(i=0;i<n;i++)
	{
		sort(ed[i].begin(),ed[i].end());
	}
	for(i=0;i<N;i++)
	{
		for(j=0;j<col[i].size();j++)
		{
			y=col[i][j];
			if(book[y]==i)
			{
				continue;
			}
			queue<int> q;
			q.push(y);
			book[y]=i;
			while(q.size())
			{
				x=q.front();
				q.pop();
				ng[x].push_back(nd);
				ng[nd].push_back(x);
				for(k=lower_bound(ed[x].begin(),ed[x].end(),make_pair(i,0))-ed[x].begin();k<ed[x].size();k++)
				{
					if(ed[x][k].F!=i)
					{
						break;
					}
					if(book[ed[x][k].S]!=i)
					{
						book[ed[x][k].S]=i;
						q.push(ed[x][k].S);
					}
				}
			}
			nd++;
		}
	}
	/*for(i=0;i<n;i++)
	{
		for(j=0;j<ng[i].size();j++)
		{
			cout<<i<<"->"<<ng[i][j]<<endl;
		}
	}*/
	queue<int> q,st;
	q.push(0);
	st.push(0);
	book[0]=-2;
	while(q.size())
	{
		x=q.front();
		y=st.front();
		q.pop();
		st.pop();
		if(x==n-1)
		{
			cout<<y/2<<endl;
			return 0;
		}
		for(i=0;i<ng[x].size();i++)
		{
			c=ng[x][i];
			if(book[c]==-2)
			{
				continue;
			}
			book[c]=-2;
			q.push(c);
			st.push(y+1);
		}
	}
	cout<<-1<<endl;
	return 0;
}