#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpii;
typedef vector <vi> vvi;

const int N = 1e3 + 5, inf = 1e9 + 7;

int n, m;
vector <pair <int, char>> adj[N];
int ck[N][N], dp[N][N];

queue <pii> qu;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> n >> m;
    ForE(i, 1, m){
        int u, v; char c; cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }
    memset(dp, 0x3f, sizeof(dp));
    ForE(i, 1, n){
        dp[i][i] = 0;
        qu.push(make_pair(i, i));
    }
    ForE(u, 1, n){
        Fora(&edge, adj[u]){
            int v = edge.fi, w = edge.se;
            if (u >= v){
                continue;
            }
            dp[u][v] = 1;
            qu.push(make_pair(u, v));
        }
    }
    while (!qu.empty()){
        int u = qu.front().fi, v = qu.front().se; qu.pop();
        if (ck[u][v]){
            continue;
        }
        ck[u][v] = 1;
        Fora(&edgeu, adj[u]){
            Fora(&edgev, adj[v]){
                int uv = edgeu.fi, uw = edgeu.se, vv = edgev.fi, vw = edgev.se;
                if (uw != vw){
                    continue;
                }
                if (uv > vv){
                    swap(uv, vv);
                }
                if (dp[uv][vv] > dp[u][v] + 2){
                    dp[uv][vv] = dp[u][v] + 2;
                    qu.push(make_pair(uv, vv));
                }
            }
        }
    }
    if (dp[1][n] == dp[N - 1][N - 1]){
        cout << -1 << endl;
    }
    else{
        cout << dp[1][n] << endl;
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/
#pragma GCC optimize("Ofast")
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define mod (int)(1e9+7)
#define mod2 998244353
#define PI 3.1415926535897932384626433832795

void solve() {
    int n; cin>>n;
    string s,t; cin>>s>>t;
    int x=0,y=0;
    for(char ch:s)
        x+=(ch=='0');
    for(char ch:t)
        y+=(ch=='0');

    if(x!=y){
        cout<<"-1\n";return;
    }
    int ans=x;
    int prefs=0,preft=0;
    for(int i=0;i<n;i++){
        prefs+=(s[i]=='0');
        preft+=(t[i]=='0');
        if(s[i]==t[i]&&s[i]=='0'&&prefs==preft)ans--;
    }
    cout<<ans;
}

int32_t main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
