#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 15;
struct edge
{
    int v,c,p,r,next;
}edges[maxn];
int head[maxn];
int vispath[maxn];
//bool vism[maxn];
int n,m,e,ans;

void addedge(int u,int v,int c,int p,int r)
{
    edges[e].v = v; edges[e].c = c; edges[e].p = p; edges[e].r = r;
    edges[e].next = head[u];
    head[u] = e++;
}

void dfs(int u,int cost)
{
    if(cost > ans) return;
    if(u == n)
    {
        if(cost < ans) ans = cost;
        return;
    }
    for(int i=head[u];i!=-1;i=edges[i].next)
    {
        int v = edges[i].v;
        if(vispath[v]<=3)
        {
            vispath[v]++;
            if(vispath[edges[i].c]>0) dfs(v,cost+edges[i].p);
            else dfs(v,cost+edges[i].r);
            vispath[v]--;
        }
    }
}

int main()
{
    int u,v,c,p,r;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        e = 0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d%d",&u,&v,&c,&p,&r);
            addedge(u,v,c,p,r);
        }
        ans = 99999999;
        memset(vispath,0,sizeof(vispath));
        memset(vism,false,sizeof(vism));
        vispath[1] = 1;
        dfs(1,0);
        if(ans < 99999999) printf("%d\n",ans);
        else printf("impossible\n");
    }
    return 0;
}