#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int MAXN = , INF = 1e9 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = ; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, M;

int tim[MAXN], dis[], B1[MAXN], B2[MAXN], F1[MAXN], F2[MAXN], vis[];

int SPFA() {

    queue<int> q;

    q.push(( << N) - ); dis[( << N) - ] = ;

    while(!q.empty()) {

        int sta = q.front(); q.pop(); vis[sta] = ;

        for(int i = ; i <= M; i++) {

            int now = sta;

            if(((sta & B1[i]) == B1[i]) && ((sta & B2[i]) == )) {

                now = now & (~F1[i]);

                now = now | F2[i];

                if(dis[now] > dis[sta] + tim[i]) {

                    dis[now] = dis[sta] + tim[i];

                    if(!vis[now]) q.push(now);

                }

            }

        }

    }

    return dis[] < INF ? dis[] : ;

}

int main() {

    N = read(); M = read();

    memset(dis, 0x3f, sizeof(dis));

    for(int i = ; i <= M; i++) {

        char s1[], s2[];

        scanf("%d %s %s", &tim[i], s1, s2);

        for(int j = ; j < N; j++)

            if(s1[j] == '+') B1[i] |=  << j;

            else if(s1[j] == '-') B2[i] |=  << j;

        for(int j = ; j < N; j++)

            if(s2[j] == '-') F1[i] |=  << j;

            else if(s2[j] == '+') F2[i] |=  << j;

    }

    printf("%d", SPFA());

    return ;

}

/*

3 3

1 000 00-

1 00- 0-+

2 0-- -++

*/