#include <iostream>
#include <queue>
using namespace std;

#define maxn 12

int n,m;			//tot答案，n：city数 m：road数
struct edge
{
	int a,b,c,p,r;
}road[maxn];

struct uu
{
	int now,money,roads;
	bool friend operator <(uu t,uu s)
	{
		return t.money>s.money;
	}
};

int dist[12][5000];

int minemine()
{
	priority_queue<uu> Q;
	uu p,q;
	p.now = 1;
	p.money = 0;
	p.roads = 2;
	Q.push(p);
	memset(dist,-1,sizeof(dist));
	while(!Q.empty())
	{
		p = Q.top();
		Q.pop();
		if(p.now==n)
			return p.money;

		if(dist[p.now][p.roads]!=-1)//如果以路径roads走到过p。不必再重复了
			continue;
		dist[p.now][p.roads]= p.money;

		for(int j =1;j<=m;j++)
		{
			if(road[j].a==p.now)//找一个从now出发的路
			{
				//先设置容易设置的now
				q.now = road[j].b;

				//下面设置roads
				q.roads = p.roads|(1<<road[j].b);
				
				if(dist[q.now][q.roads]!=-1)
					continue;
				//下面设置money
				int temp1 = 1<<road[j].c;
				if((p.roads|temp1)==p.roads)//我之前经过过C啦
						q.money = p.money+road[j].p;
				else
						q.money = p.money +road[j].r;

				//放入优先队列
				Q.push(q);
			}
		}
	}
	return -1;
}

int main()
{
	int i;
	bool hasN;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		hasN = false;
		memset(road,-1,sizeof(road));
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d%d%d",&road[i].a,&road[i].b,&road[i].c,&road[i].p,&road[i].r);
			if(road[i].b == n)
				hasN = true;//总算是可以到达的
		}
		if(n==1)
			printf("0\n");
		else if(!hasN)
			printf("impossible\n");
		else{
			//下面用优先队列做吧
			int ans = minemine();
			if(ans==-1)
				printf("impossible\n");
			else
				printf("%d\n",ans);
		}
	}
	return 0;
}