A network of m roads connects N cities (numbered from 1 to N). There may be more than one road connecting one city with another. Some of the roads are paid. There are two ways to pay for travel on a paid road ifrom city a_i to city b_i:

• in advance, in a city c_i (which may or may not be the same as a_i);
• after the travel, in the city b_i.

The payment is P_i in the first case and R_i in the second case.

Write a program to find a minimal-cost route from the city 1 to the city N.

The first line of the input contains the values of N and m. Each of the following m lines describes one road by specifying the values of a_i, b_i, c_i, P_i, R_i (1 ≤ i ≤ m). Adjacent values on the same line are separated by one or more spaces. All values are integers, 1 ≤ m, N ≤ 10, 0 ≤ P_i , R_i ≤ 100, P_i ≤ R_i (1 ≤ i ≤ m).

The first and only line of the file must contain the minimal possible cost of a trip from the city 1 to the city N. If the trip is not possible for any reason, the line must contain the word ‘impossible’.

#include<iostream>
#define Max 9999999
using namespace std;
int map[11][5],n,m,count=0,res=Max;
int p[11],pt[11]={0};
void dfs(int k){
	if(k==n){
		if(count<res) res=count;
		return ;
	}
	for(int i=1;i<=m;i++)
	if(k==map[i][0]&&pt[map[i][0]]<3){
		count+=map[i][p[map[i][2]]+3];
		int tempx=p[map[i][0]];
		p[map[i][0]]=0;
		pt[map[i][0]]++;
		if(count<res)
		dfs(map[i][1]);
		pt[map[i][0]]--;
		p[map[i][0]]=tempx;
		count-=map[i][p[map[i][2]]+3];
	}
}
int main(){
	cin>>n>>m; 
	for(int i=1;i<=m;i++) p[i]=1;
	for(int i=1;i<=m;i++)
	cin>>map[i][0]>>map[i][1]>>map[i][2]>>map[i][3]>>map[i][4];
	dfs(1);
	if(res!=Max)
	cout<<res<<endl;
	else cout<<"impossible\n";
	return 0;
}