#include <bits/stdc++.h>

using namespace std;
//#define int long long
const int maxn = 4e6;

struct node
{
    int v;
    int w;

    bool operator<(const node &s) const
    {
        return w > s.w;  //优先队列从小到大，sort从大到小
    }
};

vector<node> a[maxn];
struct N{
    int T;
    char s1[25],s2[25];
}b[105];
bool vis[maxn];
int dis[maxn];
int n,m;
void dij(int s)
{

    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    priority_queue<node> p;
    p.push(node{s, 0});

    while (!p.empty()) {
        int v = p.top().v;
        p.pop();
        if (vis[v] == 1)continue;
        vis[v] = 1;
        for (int i = 0; i < a[v].size(); i++) {
            if (!vis[a[v][i].v] && a[v][i].w + dis[v] < dis[a[v][i].v]) {
                dis[a[v][i].v] = a[v][i].w + dis[v];
                p.push(node{a[v][i].v, dis[a[v][i].v]});
            }
        }
    }
}
// 用来判断u可以和哪些点建边
int check(int u,int con)
{
    int flag = 0;
    int z = u;
    for(int i = 0;i<n;i++)
    {
        if(b[con].s1[i]=='+'&&u%2==1)
        {
            u /= 2;
            continue;
        }
        if(b[con].s1[i]=='-'&&u%2==0)
        {
            u/=2;
            continue;
        }
        if(b[con].s1[i]=='0')
        {
            u/=2;
            continue;
        }
        flag = 1;
        break;
    }
    u = z;
    int res = 0;
    queue<int>que;
    while(u)
    {
        que.push(u%2);
        u/=2;
    }
    int q[30],cnt= 0;
    while(!que.empty())
    {
        q[cnt++] = que.front();
        que.pop();
    }
    if(flag)
        return -1;
    else {
        for(int i = 0;i < n;i++)
        {
            if(b[con].s2[i] == '+')
                q[i] = 1;
            if(b[con].s2[i] == '-')
                q[i] = 0;
        }
        for (int i = 0; i < n; i++)
        {
            if(q[i] == 1)
                res +=(1<<i);
        }
    }

    return res ;
}
bool V[maxn];
void fun(int u)
{
    V[u] =true;
    for(int i = 1;i<=m;i++)
    {
        int  s = check(u,i);
        if(s!=-1&&u!=s)
        {
            a[u].emplace_back(node{s, b[i].T});
           // cout<<u<<"->"<<s<<endl;
            if(!V[s])
                fun(s);
        }
    }
}
signed main()
{

  //  freopen("1.in","r",stdin);
    cin >> n >> m ;
    int s =( 1 << n) - 1;
   // cout << s << endl;
    for(int i = 1;i<=m;i++)
       cin>>b[i].T>>b[i].s1>>b[i].s2;
    fun(s);
    dij(s);

    if(dis[0] == 0x3f3f3f3f)
    {
        cout << 0 << '\n';
        return 0;
    }
        cout<<dis[0]<<'\n';
    return 0;
}