Give you n points, m undirected edges, each edge has length d and cost p, give you start point s and end point t, and ask to output the shortest distance from the start point to the end point and its cost. If the shortest distance has multiple routes, the output cost is the least.

Input

Input n,m, the number of points is 1~n, then m lines, each line has 4 numbers a,b,d,p, which means there is an edge between a and b, and its length is d, and the cost is p. The last line is two numbers s,t; the starting point s, the ending point. Input ends when n and m are 0.
(1<n<=1000, 0<m<100000, s != t)

Output

The output line has two numbers, the shortest distance and its cost.

Sample Input

3 2
1 2 5 6
2 3 4 5
1 3
0 0

Sample Output

9 11

This is still a dijastra, but the shortest path is determined by several elements, one is the distance from the starting point to the end point, the other is the least cost, so we need to consider one more factor, that is, the cost, which is basically similar to the template of dijastra, which is a little different.

It is to judge one more step in the middle. When the distance is the same, it is to compare the cost.

Code:

 

#include<iostream>
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1005;
const int inf = 0x3f3f3f3f;

int val[maxn][maxn];	   //Map weight 
int time2[maxn][maxn];     //Map time 

int vis[maxn];       //sign 
int d1[maxn];		//Weight 
int d2[maxn];       //time 

int n,m;
void init()
{
	
	memset(vis,0,sizeof(vis));
	memset(d1,0,sizeof(d1));
	memset(d2,0,sizeof(d2));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		if(i==j)
			val[i][j]=time2[i][j]=0;
		else
			val[i][j]=time2[i][j]=inf;
	
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0&&m==0)
			break;	
			
			init();
			int a,b,d,time;
			for(int i=0;i<m;i++)
			{
				scanf("%d%d%d%d",&a,&b,&d,&time);
				if(val[a][b]>d)
				{
					val[a][b]=val[b][a]=d;
					time2[a][b]=time2[b][a]=time;
				}
			}
			int start,end;
			scanf("%d%d",&start,&end);
		for(int i=1;i<=n;i++)
			d1[i]=val[start][i];
		for(int i=1;i<=n;i++)
			d2[i]=time2[start][i];
		int pos;
			
		
		for(int i=0;i<=n;i++)
		{
			int minv=inf;
			for(int j=1;j<=n;j++)
			if(!vis[j]&&minv>d1[j])
			{
				pos=j;
				minv=d1[j];
			}
			vis[pos]=1;
			for(int j=1;j<=n;j++)
			{
				if(!vis[j]&&d1[j]>val[pos][j]+minv)
				{
					d1[j]=minv+val[pos][j];
					d2[j]=time2[pos][j]+d2[pos];
				}
				else if(!vis[j]&&d1[j]==val[pos][j]+minv)
				{
					if(d2[j]>time2[pos][j]+d2[pos])
						d2[j]=time2[pos][j]+d2[pos];
				}
				
			}
			
		}	
		
		printf("%d %d\n",d1[end],d2[end]);
	}
	
	
	
	return 0;
}