/*申请二维数组空间, 大小为n*n
　　@param n 二维数组空间的 大小
　　@result 返回一个 (n+1)*(n+1) 大小的 二维数组,下标从1开始到n
　　*/
　　int** apply_malloc(int n)
　　{
　　int **p;
　　int i;
　　p = (int**)malloc(sizeof(int)*(n+1));
　　for(i = 0; i<=n; ++i)
　　{
　　p[i] = (int *)malloc(sizeof(int)*(n+1));
　　}
　　return p;
　　}
　　/*初始化二维数组
　　@param gp 存储路径权值
　　@param gm 存储花费权值
　　*/
　　int init(int **gp, int **gm, int n)
　　{
　　int i = 1,j = 1;
　　for(i = 1;i <= n; ++i)
　　{
　　for(j = i; j <= n; ++j)
　　{
　　gp[i][j] = NIL;
　　gp[j][i] = NIL;
　　gm[i][j] = NIL;
　　gm[j][i] = NIL;
　　}
　　}
　　return 1;
　　}
　　/**
　　Dijkstra 算法
　　*/
　　int dijkstra(int ** gp, int ** gm, int s, int n)
　　{
　　int flag = n;
　　int index = 0;
　　int i,j,min;
　　init_shortpath_source(n,s);
　　while(flag--)
　　{
　　/*查找集合 0 中,路径上界最小的结点*/
　　for(i = 1; i <= n; ++i)
　　{
　　if(node[i].flag == 0)
　　{
　　min = node[i].d;
　　index = i;
　　break;
　　}
　　}
　　for(++i; i <= n; ++i)
　　{
　　if(node[i].flag == 0 && min > node[i].d)
　　{
　　min = node[i].d;
　　index = i;
　　}
　　}
　　/*将该点 加入 1 集合*/
　　node[index].flag = 1;
　　/*对每个以该点为起点的路径进行松弛操作*/
　　for(j = 1; j <= n; ++j)
　　{
　　if(node[j].flag == 0 && gp[index][j] != NIL)
　　{
　　relax(index,j,gp,gm);
　　}
　　}
　　}
　　return 1;
　　}
　　/*打印一个二维数组*/
　　int printf_array_2(int ** array, int n)
　　{
　　int i,j;
　　for(i = 1; i <= n; ++i)
　　{
　　for(j = 1; j <= n; ++j)
　　{
　　printf("%d\t", array[i][j]);
　　}
　　printf("\n");
　　}
　　return 1;
　　}
　　/*主方法*/
　　int main()
　　{
　　int n,m,a,b,p,q,i,s,e;
　　int **gp, **gm;
　　/*输入 结点个数, */
　　scanf("%d%d",&n,&m);
　　while(n||m)
　　{
　　/*申请两个二维数组空间, 一个存放路径权值, 一个存放花费权值*/
　　gp = apply_malloc(n);
　　gm = apply_malloc(n);
　　/*初始化二维表*/
　　init(gp,gm,n);
　　for(i = 1; i <= m; ++i)
　　{
　　/*输入路径和花费*/
　　scanf("%d%d%d%d",&a,&b,&p,&q);
　　/*解决有多条路径的问题,取权值最小的一条路径进行运算*/
　　if(gp[a][b] > p)
　　{
　　gp[a][b] = p;
　　gm[a][b] = q;
　　gp[b][a] = p;
　　gm[b][a] = q;
　　}
　　/*解决多条路径具有相同权值问题,取花费最小的一条路径进行运算*/
　　else if(gp[a][b] == p && gm[a][b] > q)
　　{
　　gm[a][b] = q;
　　gm[b][a] = q;
　　}
　　}
　　/*输入源点和终点*/
　　scanf("%d%d",&s,&e);
　　/*进行Dijkstra运算*/
　　dijkstra(gp,gm,s,n);
　　/*输出结果*/
　　printf("%d %d\n",node[e].d, node[e].m);
　　/*释放空间*/
　　free(gm);
　　free(gp);
　　/*等待下组数据*/
　　scanf("%d%d",&n,&m);
　　}
　　}