Problem Description
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define INF 0x7f7f7f7f///初始化巨坑，0x7fffffff会报错
#define maxn 1005
using namespace std;

int dis[maxn];
int spend[maxn];
int cost[maxn][maxn];
int Map[maxn][maxn];
bool vis[maxn];
int n,m;

void init()
{
    memset(vis,false,sizeof(vis));
    for(int i = 1;i <= 1004;i++)
    {
        dis[i]=INF;
        spend[i]=INF;
        for(int j = 1;j <= 1004;j++)
            cost[i][j]=Map[i][j]=INF;
    }
}

void dij(int st,int en)///dij模板
{
    dis[st]=0;
    spend[st]=0;
    for(int i = 1;i <= n;i++)
    {
        int minn = INF;
        int mark;
        for(int j = 1;j <= n;j++)
        {
            if(!vis[j] && dis[j] <= minn)
            {
                minn = dis[j];
                mark = j;
            }
        }
        if(minn == INF) break;
        vis[mark]=true;
        for(int j = 1;j <= n;j++)
        {
            if(!vis[j] && dis[j] > dis[mark]+Map[mark][j])
            {
                dis[j] = dis[mark]+Map[mark][j];
                spend[j] = spend[mark]+cost[mark][j];
            }
            else if(dis[j] == dis[mark]+Map[mark][j] && spend[j] > spend[mark]+cost[mark][j])
                spend[j] = spend[mark]+cost[mark][j];
        }
    }
}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)
            break;
        int a,b,d,p;
        init();
        while(m--)
        {
            scanf("%d%d%d%d",&a,&b,&d,&p);
            if(a!=b&&Map[a][b]>d)///这里的与cost没有关系
            {
                Map[a][b]=Map[b][a]=d;
                cost[a][b]=cost[b][a]=p;
            }
        }
        int st,en;
        scanf("%d%d",&st,&en);
        dij(st,en);
        printf("%d %d\n",dis[en],spend[en]);
    }
    return 0;
}