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

typedef long long ll;
typedef long double ld;

const int N = 1e5 + 5;
const int M = 2000 + 5;
const int OO = 1e9;
const int mod = 1e9 + 7;

string s[3];
set<char> st;

int main() {

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

    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
    #endif

    for (auto & i : s) {
        cin >> i;
        for(auto & c : i) {
            st.insert(c);
        }
    }
    if(st.size() > 10) {
        cout << "UNSOLVABLE\n";
    } else {
        char dummy = 0;
        bool found = false;
        while(st.size() < 10) {
            st.insert(dummy++);
        }
        vector<char> v;
        v.reserve(st.size());
        for(auto & i : st) {
            v.push_back(i);
        }
        do {
            map<char, int> val;
            for (int i = 0; i < v.size(); ++i) {
                val[v[i]] = i;
            }
            string n[3];
            bool hasLeadingZeros = false;
            for (int i = 0; i < 3; ++i) {
                n[i].reserve(s[i].size());
                for(auto & c : s[i]) {
                    n[i].push_back(val[c] + '0');
                }
                hasLeadingZeros |= (n[i].front() == '0');
            }
            if(!hasLeadingZeros) {
                ll a = stoll(n[0]);
                ll b = stoll(n[1]);
                ll c = stoll(n[2]);
                if(a + b == c) {
                    for(auto & i : n) {
                        cout << i << '\n';
                    }
                    found = true;
                    break;
                }
            }

        } while(next_permutation(v.begin(), v.end()));
        if(!found) {
            cout << "UNSOLVABLE\n";
        }
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "../debug.h"
#else
#define debug(x...) 141
#endif
#define forn(i,x,n) for(int i = x; i < n; ++i)
#define forit(it, m) for(auto it = m.begin(); it!=m.end(); ++it)
typedef long long ll;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,mm,x,y,ans=1e9;
    char c;

    cin>>n>>mm;
    map<char,vector<pair<int,int>>> m;
    set<pair<int,int>> edges;
    map<pair<int,int>,int> dist;

    forn(i,0,mm){
    	cin>>x>>y>>c;
    	edges.insert({x-1,y-1});
    	edges.insert({y-1,x-1});
    	m[c].push_back({x-1,y-1});
    	m[c].push_back({y-1,x-1});
    }

    map<pair<int,int>,vector<pair<int,int>>> adj;

    for(auto x:m)
    	for(auto [a,b]:x.second)
    		for(auto [c,d]:x.second)
    			adj[{a,c}].push_back({b,d});

    queue<pair<int,int>> q;
    q.push({0,n-1});
    dist[{0,n-1}]=0;
    while(q.size()){
    	auto [u,v]=q.front();
    	q.pop();
    	if(edges.count({u,v}))
    		ans=min(ans,1+dist[{u,v}]);
    	if(u==v)
    		ans=min(ans,dist[{u,v}]);
    	for(auto [a,b]:adj[{u,v}])
    		if(!dist.count({a,b}))
    			q.push({a,b}), dist[{a,b}]=dist[{u,v}]+2;
    }


    cout<<(ans==1e9?-1:ans)<<'\n';
    
    return 0;
}