> #include <iostream>
> #include <cstdio>
> #include <cstring>
> using namespace std;
> int fac[12];
> int n, m;
> struct node{
> 	int to, cost1, cost2, need, next;
> }path[120];
> int npath;
> int first[11];
> 
> struct qnode{
> 	int p, s, d;
> 	qnode(){}
> 	qnode(int p, int s, int d):p(p), s(s), d(d){}
> 	bool friend operator < (qnode &a, qnode &b){
> 		return a.d<b.d;
> 	}
> }queue[10000];
> int size;
> void push(qnode a){
> 	int i=++size;
> 	for(; i>1 && a<queue[i>>1]; i>>=1)
> 	queue[i]=queue[i>>1];
> 	queue[i]=a;
> }
> qnode pop(){
> 	qnode min=queue[1], last=queue[size--];
> 	int i=1, child;
> 	for(; (i<<1)<=size; i=child){
> 		child=i<<1;
> 		if(child!=size && queue[child+1]<queue[child]) child++;
> 		if(last<queue[child]) break;
> 		queue[i]=queue[child];
> 	}
> 	queue[i]=last;
> 	return min;
> }
> 
> int dist[11][1024];
> int dijkstra()
> {
> 	int u, v, d, s;
> 	qnode tmp;
> 	memset(dist, -1, sizeof(dist));
> 	size=0;
> 	push(qnode(1, 1, 0));
> 	while(size>0){
> 		tmp=pop();
> 		u=tmp.p; d=tmp.d; s=tmp.s;
> 		if(dist[u][s]!=-1) continue;
> 		if(u==n) return d;
> 		dist[u][s]=d;
> 		for(int i=first[u]; i!=-1; i=path[i].next){
> 			v=path[i].to;
> 			if(dist[v][s|fac[v]]!=-1) continue;
> 			if(s&fac[path[i].need]) push(qnode(v, s|fac[v], d+path[i].cost1));
> 			else push(qnode(v, s|fac[v], d+path[i].cost2));
> 		}
> 	}
> 	return -1;
> }
> void init(){
> 	fac[1]=1;
> 	for(int i=2; i<=10; i++)
> 	fac[i]=2*fac[i-1];
> }
> int main(){
> 	init();
> 	int a;
> 	npath=0;
> 	memset(first, -1, sizeof(first));
> 	scanf("%d %d", &n, &m);
> 	for(int i=0; i<m; i++){
> 		scanf("%d %d %d %d %d", &a, &path[npath].to, &path[npath].need, &path[npath].cost1, &path[npath].cost2);
> 		path[npath].next=first[a];
> 		first[a]=npath++;
> 	}
> 	a=dijkstra();
> 	if(a==-1) printf("impossible\n");
> 	else printf("%d\n", a);
> 	return 0;
> }
>