#include <iostream>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;

vector< pair<int,int> > V;
vector< pair< pair<int,int>,int> > E;
vector<pair<int,int> > G[500005];
int dist[500005];

map<pair<int,int>,int> mp;
int main(){
    int N,M;
    cin>>N>>M;
    for(int i = 0;i < M;i++){
        int p,q,c;
        cin>>p>>q>>c;
        E.push_back(make_pair(make_pair(p,q),c));
        V.push_back(make_pair(p,c));
        V.push_back(make_pair(q,c));
    }
    for(int i = 1;i <= N;i++){V.push_back(make_pair(i,0));}
    for(int i = 0;i<500005;i++)dist[i]=-1;
    sort(V.begin(),V.end());
    V.resize(unique(V.begin(),V.end()) -V.begin());
    int vsize = V.size();
    for(int i = 0;i < vsize;i++){
        mp[V[i]]=i;
    }
    for(int i = 0;i < E.size();i++){
        int p,q,c;
        p=E[i].first.first;
        q=E[i].first.second;
        c=E[i].second;
        G[mp[make_pair(p,c)]].push_back(make_pair(0,mp[make_pair(q,c)]));
        G[mp[make_pair(q,c)]].push_back(make_pair(0,mp[make_pair(p,c)]));
        G[mp[make_pair(p,c)]].push_back(make_pair(0,mp[make_pair(p,0)]));
        G[mp[make_pair(p,0)]].push_back(make_pair(1,mp[make_pair(p,c)]));
        G[mp[make_pair(q,c)]].push_back(make_pair(0,mp[make_pair(q,0)]));
        G[mp[make_pair(q,0)]].push_back(make_pair(1,mp[make_pair(q,c)]));
    }
    priority_queue<pair<int,int> ,vector<pair<int,int> > ,greater<pair<int,int> > > pq;
    pq.push(make_pair(0,mp[make_pair(1,0)]));
    while(!pq.empty()){
        pair<int,int> top = pq.top();
        pq.pop();
        int d = top.first;
        int v = top.second;
        //cout<<"a: "<<d<<" "<<V[v].first<<" "<<V[v].second<<" "<<endl;
        if(dist[v]==-1||dist[v] > d){
            dist[v] = d;
            for(int i = 0; i < G[v].size(); i++){
                pq.push(make_pair(G[v][i].first + d, G[v][i].second));
            }
        }
    }
    cout<<dist[mp[make_pair(N,0)]]<<endl;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    vector<int>v(m + 3), v2, stick(12), val(12, -1), vis(12, 0);
    stick[1] = 2, stick[2] = 5, stick[3] = 5, stick[4] = 4, stick[5] = 5, stick[6] = 6, stick[7] = 3, stick[8] = 7, stick[9] = 6;
    for(int i = 0; i < m; i++){
        cin >> v[i];
        if(vis[stick[v[i]]] == 0){
            vis[stick[v[i]]] = 1;
            v2.push_back(stick[v[i]]);
        }
        val[stick[v[i]]] = max(val[stick[v[i]]], v[i]);
    }
    int dp[n + 3];
    for(int i = 0; i <= n; i++){
        dp[i] = -1;
    }
    dp[0] = 0;
    for(int i = 0; i < v2.size(); i++){
        for(int j = v2[i]; j <= n; j++){
            if(dp[j - v2[i]] != -1){
                dp[j] = max(dp[j], dp[j - v2[i]] + 1);
            }
        }
    }
    vector<pair<int, int> >vec;
    for(int i = 0; i < v2.size(); i++){
        vec.push_back(make_pair(val[v2[i]], v2[i]));
    }
    sort(vec.rbegin(), vec.rend());
    string s;
    int cnt = 0;
    while(n > 0){
        cnt++;
        for(int j = 0; j < vec.size(); j++){
            if(n - vec[j].second >= 0 && dp[n] == dp[n - vec[j].second] + 1){
                s.push_back('0' + vec[j].first);
                n = n - vec[j].second;
                break;
            }
        }
    }
    cout << s;
    return 0;
}