#include <stdio.h>
#include <string.h>
int N,m;
structnode
{
    int a,b;
    int ci,pi,ri;
}maps[20];
int minS,flag[11];
void dfs(int pos,int res)
{
    if(pos==N)
    {
        if(res<minS)
            minS=res;
        return;
    }
    for(int i=1;i<=m;i++)
    {
        if(pos==maps[i].a && flag[maps[i].b]<=3)
        {
            int b=maps[i].b;
            flag[b]++;
            if(flag[maps[i].ci])
                dfs(b,res+maps[i].pi);
            else
                dfs(b,res+maps[i].ri);
            flag[b]--;
        }
    }
    return;
}
int main()
{
    while(~scanf("%d%d",&N,&m))
    {
        int i;
        for(i=1;i<=m;i++)
            scanf("%d%d%d%d%d",&maps[i].a,&maps[i].b,&maps[i].ci,&maps[i].pi,&maps[i].ri);
        minS=0xfffffff;
        memset(flag,0,sizeof(flag));
        flag[1]=1;
        dfs(1,0);
        if(minS==0xfffffff)
            printf("impossible\n");
        else
            printf("%d\n",minS);
    }
    return 0;
}

poj paid road(DFS)