#include <iostream>
#include <stdio.h>
using namespace std;

int adjNum[11] = {0};
int adjList[11][11];
int adjCost[11][11];
int adjDisCost[11][11];
int adjDisArg[11][11];
int adjState[11] = {1, 0};

bool contain(int state, int bit){
	return ((state & (1<<bit)) != 0);
}

void dfs(int lab, bool *used){
	used[lab] = 1;
	for(int i = 0; i < adjNum[lab]; i++){
		int tar = adjList[lab][i];
		if(used[tar]) continue;
		dfs(tar, used);
	}
}

int main() {
	int cost[10][1024];
	int n, m;
	scanf("%d%d", &n, &m);
	int n2 = (1 << n);
	for(int i = 0; i < n; i++){
		for(int j = 1; j < n2; j+=2){
			cost[i][j] = 10000000;
		}
	}
	cost[0][1] = 0;

	for(int i = 0; i < m; i++){
		int from, to, pay, lowprice, price;
		scanf("%d%d%d%d%d", &from, &to, &pay, &lowprice, &price);
		from--, to--, pay--;
		if(from == to) continue;
		adjList[to][adjNum[to]] = from;
		adjCost[to][adjNum[to]] = price;
		adjDisCost[to][adjNum[to]] = lowprice;
		adjDisArg[to][adjNum[to]] = pay;
		adjState[to] += (1 << from);
		adjNum[to]++;
	}
	if(n == 1){
		printf("0\n");
		return 0;
	}
	bool used[11] = {0};
	dfs(n-1, used);
	if(!used[0]){
		printf("impossible\n");
		return 0;
	}
	while(1){
		bool ybd = 0;
		//cout << 1 << endl;
		for(int st = 1; st < n2; st += 2){
			for(int p = 0; p < n; p++){
				if(p == 0 && st == 1) continue;
				if(!contain(st, p) || ((st & adjState[p]) == 0)) continue;
				int mn = cost[p][st];
				for(int i = 0; i < adjNum[p]; i++){
					int v = adjList[p][i];
					int c = adjCost[p][i];
					int lc = adjDisCost[p][i];
					int arg = adjDisArg[p][i];
					int st_ = st - (1 << p);
					int tempD = cost[v][st] + (contain(st, arg) ? lc : c);
					if(tempD < mn){
						ybd = 1;
						mn = tempD;
					}
					if(p != 0){
						tempD = cost[v][st_] + (contain(st_, arg) ? lc : c);
						if(tempD < mn){
							ybd = 1;
							mn = tempD;
						}
					}
				}
				cost[p][st] = mn;
			}
		}
		if(!ybd) break;
	}
	int minC = 10000000;
	for(int st = 1 + (1 << (n-1)); st < n2; st += 2){
		if(cost[n-1][st] < minC) minC = cost[n-1][st];
	}
	printf("%d\n", minC);
	return 0;
}