//Date: 2025-01-18 18:48:18
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P emplace_back
#define CLEAR(a,v) memset((a),(v),sizeof((a)))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
//char buf[1<<20],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
bool MBE;
namespace SOLVER {
const int M=29989,inv2=(M+1)/2;
int qpow(int x,int y=M-2) {int s=1;for(;y;y>>=1,x=x*x%M) if(y&1) s=s*x%M;return s;}
int n,m,w;int a[75][75][(1<<12)+5],ans[(1<<12)+5];char s[15];
inline void FWT(int f[],int op) {
    for(int i=1,t=0;t<w;i<<=1,t++) for(int j=0;j<(1<<w);j+=(i<<1)) rep(k,0,i-1) {
        if(s[t]=='|') f[i+j+k]=(f[i+j+k]+f[j+k]*op+M)%M;
        if(s[t]=='&') f[j+k]=(f[j+k]+f[i+j+k]*op+M)%M;
        if(s[t]=='^') {
            int X=f[j+k],Y=f[i+j+k],K=(op==1?1:inv2);
            f[j+k]=((X+Y)*K%M+M)%M,f[i+j+k]=((X-Y)*K%M+M)%M;
        }
    }
}
inline int getval(int v) {
    int ans=1,fl=1;rep(i,1,n) {
        rep(j,i,n) if(a[j][i][v]) {
            if(i==j) break;ans*=-1;
            rep(k,i,n) swap(a[i][k][v],a[j][k][v]);break;
        }
        ans=ans*a[i][i][v]%M;int res=qpow(a[i][i][v]);rep(j,i,n) a[i][j][v]=a[i][j][v]*res%M;
        rep(j,i+1,n) rep(k,i,n) a[j][k][v]=(a[j][k][v]-a[j][i][v]*a[i][k][v])%M;
    }return ans;
}
void MAIN() {
    scanf("%d%d%s",&n,&m,s);n--;w=strlen(s);
    rep(i,1,m) {
        int x=rd()-1,y=rd()-1,v=rd();if(x==y) continue;
        a[x][x][v]++,a[y][y][v]++,a[x][y][v]--,a[y][x][v]--;
    }
    rep(i,1,n) rep(j,1,n) FWT(a[i][j],1);rep(i,0,(1<<w)) ans[i]=getval(i);
    FWT(ans,-1);per(i,(1<<w)-1,0) if(ans[i]) {cout<<i<<endl;return;}puts("-1");
}
}
bool MED;
signed main() {
    //freopen(".in","r",stdin);freopen(".out","w",stdout);
    for(int tt=1;tt;tt--) SOLVER::MAIN();
    cerr<<(&MBE-&MED)/1024<<" KB, "<<1000*clock()/CLOCKS_PER_SEC<<" ms\n";
    return 0;
}