#include <cstdio>
#include <cstring>
using namespace std;

#define MAXN 11
#define MAXM 100
#define INF 10000

int pi[MAXM];//间接访问代价
int ri[MAXM];//直接访问代价
int p[MAXM];//需要间接访问的点
int s[MAXM];//边列表
int e[MAXM];
int vi[MAXN];//点是否被访问
bool ans;//是否存在结果
int n,m;
int res;

void BFS(int st,int cp,int c)
{
	int i;
	int j;
	int tp;
	//for(j=1;j<=c;j++)printf("  ");
	//printf("start=%d cp=%d\n",st,cp);
	for(i=1;i<=m;i++)
	{
		if(s[i]==st)
		{
			//for(j=1;j<=c;j++)printf("  ");
			//printf("i=%d e[i]=%d\n",i,e[i]);
			if(vi[p[i]]>0)
			{
				tp=cp;
				tp+=ri[i]>pi[i]?pi[i]:ri[i];
			}
			else
				tp=cp+ri[i];
			//for(j=1;j<=c;j++)printf("  ");
			//printf("tp=%d\n",tp);
			if(tp>res)
				return;
			if(e[i]==n)
			{
				ans=true;
				if(res>tp)
					res=tp;
				//for(j=1;j<=c;j++)printf("  ");
				//printf("res=%d\n",res);
			}
			vi[e[i]]++;
			//for(j=1;j<=c;j++)printf("  ");
			//printf("into %d\n",e[i]);
			BFS(e[i],tp,c+1);
			//for(j=1;j<=c;j++)printf("  ");
			//printf("back %d\n",st);
			vi[e[i]]--;
		}
	}
}

int main()
{
	int i;

	scanf("%d%d",&n,&m);

	
	for(i=1;i<=m;i++)
		scanf("%d%d%d%d%d",&s[i],&e[i],&p[i],&pi[i],&ri[i]);
	if(n==1)
	{
		printf("0\n");
		return 0;
	}
	memset(vi,0,sizeof(vi));
	res=INF;
	vi[1]=1;
	ans=false;
	BFS(1,0,0);
	if(ans)
		printf("%d\n",res);
	else
		printf("impossible\n");
	return 0;
}