//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define up upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m;
int u[2005];
int v[2005];
char c[2005];

vector<ii> al[1005][1005];

bool adj[1005][1005];
int w[1005][1005];
queue<ii> q;

int ans=1e9;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>m;
	rep(x,0,m) cin>>u[x]>>v[x]>>c[x],adj[u[x]][v[x]]=adj[v[x]][u[x]]=true;
	rep(x,m,2*m) u[x]=v[x-m],v[x]=u[x-m],c[x]=c[x-m];
	
	rep(x,0,2*m) rep(y,0,2*m) if (c[x]==c[y]){
		al[u[x]][u[y]].pub(ii(v[x],v[y]));
	}
	
	memset(w,63,sizeof(w));
	w[1][n]=0;
	q.push(ii(1,n));
	
	int a,b;
	while (!q.empty()){
		tie(a,b)=q.front();
		q.pop();
		
		if (a==b) ans=min(ans,w[a][b]*2);
		else if (adj[a][b]) ans=min(ans,w[a][b]*2+1);
		
		int c,d;
		for (auto &it:al[a][b]){
			tie(c,d)=it;
			if (w[c][d]>1e9){
				w[c][d]=w[a][b]+1;
				//cout<<"from: "<<a<<"-"<<b<<" to: "<<c<<"-"<<d<<endl;
				q.push(ii(c,d));
			}
		}
	}
	
	if (ans==1e9) cout<<"-1"<<endl;
	else cout<<ans<<endl;
}

#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
const int INF = INT_MAX / 3;

int dp[1 << 17][17];

void solve() {
    int N;
    cin >> N;
    vi X(N), Y(N), Z(N);
    rep(i, N) {
        cin >> X[i] >> Y[i] >> Z[i];
    }
    rep(S, 1 << N)rep(i, N)dp[S][i] = INF;
    dp[1][0] = 0;
    rep(S, 1 << N) {
        rep(i, N) {
            rep(j, N) {
                int d = abs(X[i] - X[j]) + abs(Y[i] - Y[j]) + max(0, Z[j] - Z[i]);
                smin(dp[S | 1 << j][j], dp[S][i] + d);
            }
        }
    }
    cout << dp[(1 << N) - 1][0] << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}