#include <bits/stdc++.h>

using namespace std;
const int INF=999999999;
int n,m,c1,c2;
int e[510][510],weight[510],w[510];
int d[510],num[510];
bool vis[510];
void Dijkstra(int s)
{
    fill(d,d+510,INF);
    d[s]=0;
    w[s]=weight[s];
    num[s]=1;
    for(int i=0;i<n;i++){
        int u=-1,mind=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<mind){
                u=j;
                mind=d[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&e[u][v]!=0){
                if(d[u]+e[u][v]<d[v]){
                    d[v]=d[u]+e[u][v];
                    w[v]=w[u]+weight[v];
                    num[v]=num[u];
                }else if(d[u]+e[u][v]==d[v]){
                    if(w[v]<w[u]+weight[v])
                        w[v]=w[u]+weight[v];
                    num[v]+=num[u];
                }
            }
        }
    }
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif
    int a,b,dist;
    cin>>n>>m>>c1>>c2;
    for(int i=0;i<n;i++) cin>>weight[i];
    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>dist;
        e[a][b]=e[b][a]=dist;
    }
    Dijkstra(c1);
    cout<<num[c2]<<" "<<w[c2];
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int INF=999999999;
int cmax,n,sp,m;
int e[510][510],weight[510],numPath=0;
int d[510],minNeed=INF,minRemain=INF;
vector<int> pre[510];
vector<int> tempPath,path;
bool vis[510];
void Dijkstra(int s)
{
    fill(d,d+510,INF);
    d[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,mind=INF;
        for(int j=0;j<=n;j++){
            if(vis[j]==false&&d[j]<mind){
                u=j;
                mind=d[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<=n;v++){
            if(vis[v]==false&&e[u][v]!=0){
                if(d[u]+e[u][v]<d[v]){
                    d[v]=d[u]+e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(d[u]+e[u][v]==d[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}
void dfs(int v)
{
    if(v==0){
        tempPath.push_back(v);
        int need=0,remain=0;
        for(int i=tempPath.size()-1;i>=0;i--){
            int id=tempPath[i];
            if(weight[id]>0)
                remain+=weight[id];
            else{
                if(remain>abs(weight[id]))
                    remain-=abs(weight[id]);
                else{
                    need+=abs(weight[id])-remain;
                    remain=0;
                }
            }
        }
        if(need<minNeed){
            minNeed=need;
            minRemain=remain;
            path=tempPath;
        }else if(need==minNeed&&remain<minRemain){
            minRemain=remain;
            path=tempPath;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(v);
    for(int i=0;i<pre[v].size();i++)
        dfs(pre[v][i]);
    tempPath.pop_back();
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif
    int a,b,dist;
    cin>>cmax>>n>>sp>>m;
    for(int i=1;i<=n;i++){
        cin>>weight[i];
        weight[i]-=cmax/2;
    }
    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>dist;
        e[a][b]=e[b][a]=dist;
    }
    Dijkstra(0);
    dfs(sp);
    cout<<minNeed<<" ";
    for(int i=path.size()-1;i>=0;i--){
        cout<<path[i];
        if(i>0) cout<<"->";
    }
    cout<<" "<<minRemain;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int INF=999999999;
int n,m,st,ed;
int e[510][510],cost[510][510];
int d[510],minCost=INF;
vector<int> pre[510];
vector<int> tempPath,path;
bool vis[510];
void Dijkstra(int s)
{
    fill(d,d+510,INF);
    d[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,mind=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<mind){
                u=j;
                mind=d[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&e[u][v]!=0){
                if(d[u]+e[u][v]<d[v]){
                    d[v]=d[u]+e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(d[u]+e[u][v]==d[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}
void dfs(int v)
{
    if(v==st){
        int tempcost=0;
        tempPath.push_back(v);
        for(int i=tempPath.size()-1;i>0;i--){
            int id=tempPath[i],idnext=tempPath[i-1];
            tempcost+=cost[id][idnext];
        }
        if(tempcost<minCost){
            minCost=tempcost;
            path=tempPath;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(v);
    for(int i=0;i<pre[v].size();i++)
        dfs(pre[v][i]);
    tempPath.pop_back();
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif
    int a,b,dist,costt;
    cin>>n>>m>>st>>ed;
    for(int i=0; i<m; i++)
    {
        cin>>a>>b>>dist>>costt;
        e[a][b]=e[b][a]=dist;
        cost[a][b]=cost[b][a]=costt;
    }
    Dijkstra(st);
    dfs(ed);
    for(int i=path.size()-1;i>=0;i--){
        cout<<path[i]<<" ";
    }
    cout<<d[ed]<<" "<<minCost;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int INF=999999999;
int n,m,k,ds;
double e[1020][1020],cost[1020][1020];
double d[1020],minCost=INF;
vector<int> pre[1020];
vector<int> tempPath,path;
bool vis[1020];
void Dijkstra(int s)
{
    fill(vis,vis+1020,false);
    fill(d,d+1020,INF);
    d[s]=0;
    for(int i=0;i<n+m;i++){
        int u=-1,mind=INF;
        for(int j=1;j<=n+m;j++){
            if(vis[j]==false&&d[j]<mind){
                u=j;
                mind=d[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=1;v<=n+m;v++){
            if(vis[v]==false&&e[u][v]!=0){
                if(d[u]+e[u][v]<d[v]){
                    d[v]=d[u]+e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(d[u]+e[u][v]==d[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif
    string s1,s2;
    cin>>n>>m>>k>>ds;
    for(int i=0; i<k; i++)
    {
        int a,b;
        double dist;
        cin>>s1>>s2>>dist;
        if(s1[0]!='G')
            a=stoi(s1);
        else
            a=n+stoi(s1.substr(1));
        if(s2[0]!='G')
            b=stoi(s2);
        else
            b=n+stoi(s2.substr(1));
        e[a][b]=e[b][a]=dist;
    }
    double ansDis=-1,ansAvg=INF;
    int ansID=-1;
    for(int i=n+1;i<=n+m;i++){
        double minDis=INF,avg=0;
        Dijkstra(i);
        for(int j=1;j<=n;j++){
            if(d[j]>ds){
                minDis=-1;
                break;
            }
            if(minDis>d[j]) minDis=d[j];
            avg+=d[j]*1.0/n;
        }
        if(minDis==-1) continue;
        if(minDis>ansDis){
            ansDis=minDis;
            ansID=i;
            ansAvg=avg;
        }else if(minDis==ansDis&&avg<ansAvg){
            ansID=i;
            ansAvg=avg;
        }
    }
    if(ansID==-1) cout<<"No Solution";
    else{
        printf("G%d\n",ansID-n);
        printf("%.1f %.1f",ansDis,ansAvg);
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int MAXV=510;
const int INF=1000000000;

int n,m,k,st,G[MAXV][MAXV],weight[MAXV];
int d[MAXV],numPath,maxW;
double maxAvg;
bool vis[MAXV];
vector<int> pre[MAXV];
vector<int> tempPath,path;
map<string,int> cityToIndex;
map<int,string> indexToCity;

void Dijkstra(int s)
{
    fill(d,d+MAXV,INF);
    d[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,MIN=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<MIN){
                u=j;
                MIN=d[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF){
                if(d[u]+G[u][v]<d[v]){
                    d[v]=d[u]+G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(d[v]==d[u]+G[u][v])
                    pre[v].push_back(u);
            }
        }
    }
}
void DFS(int v)
{
    if(v==st){
        tempPath.push_back(v);
        numPath++;
        int tempW=0;
        for(int i=tempPath.size()-2;i>=0;i--){
            int id=tempPath[i];
            tempW+=weight[id];
        }
        double tempAvg=1.0*tempW/(tempPath.size()-1);
        if(tempW>maxW){
            maxW=tempW;
            maxAvg=tempAvg;
            path=tempPath;
        }else if(tempW==maxW&&tempAvg>maxAvg){
            maxAvg=tempAvg;
            path=tempPath;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(v);
    for(int i=0;i<pre[v].size();i++)
        DFS(pre[v][i]);
    tempPath.pop_back();
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif
    string start,city1,city2;
    cin>>n>>m>>start;
    cityToIndex[start]=0;
    indexToCity[0]=start;
    for(int i=1;i<=n-1;i++){
        cin>>city1>>weight[i];
        cityToIndex[city1]=i;
        indexToCity[i]=city1;
    }
    fill(G[0],G[0]+MAXV*MAXV,INF);
    for(int i=0;i<m;i++){
        cin>>city1>>city2;
        int c1=cityToIndex[city1],c2=cityToIndex[city2];
        cin>>G[c1][c2];
        G[c2][c1]=G[c1][c2];
    }
    Dijkstra(0);
    int rom=cityToIndex["ROM"];
    DFS(rom);
    cout<<numPath<<" "<<d[rom]<<" "<<maxW<<" "<<(int)maxAvg<<endl;
    for(int i=path.size()-1;i>=0;i--){
        cout<<indexToCity[path[i]];
        if(i>0) cout<<"->";
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int INF=999999999;
int n,m,st,fin;
int e[510][510],w[510][510],dispre[510],Timepre[510];
int dis[510],Time[510];
int weight[510],nodenum[510];
vector<int> dispath,Timepath;
bool vis[510];
void dfsdispath(int v)
{
    dispath.push_back(v);
    if(v==st) return;
    dfsdispath(dispre[v]);
}
void dfsTimepath(int v)
{
    Timepath.push_back(v);
    if(v==st) return;
    dfsTimepath(Timepre[v]);
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif
    fill(dis,dis+510,INF);
    fill(Time,Time+510,INF);
    fill(weight,weight+510,INF);
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int a,b,one;
        cin>>a>>b>>one;
        cin>>e[a][b]>>w[a][b];
        if(one!=1){
            e[b][a]=e[a][b];
            w[b][a]=w[a][b];
        }
    }
    cin>>st>>fin;
    dis[st]=0;
    for(int i=0;i<n;i++){
        int u=-1,minn=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&dis[j]<minn){
                u=j;
                minn=dis[j];
            }
        }
        if(u==-1) break;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&e[u][v]!=0){
                if(dis[u]+e[u][v]<dis[v]){
                    dis[v]=dis[u]+e[u][v];
                    dispre[v]=u;
                    weight[v]=weight[u]+w[u][v];
                }else if(dis[u]+e[u][v]==dis[v]&&weight[v]>weight[u]+w[u][v]){
                    dispre[v]=u;
                    weight[v]=weight[u]+w[u][v];
                }
            }
        }
    }
    dfsdispath(fin);
    Time[st]=0;
    fill(vis,vis+510,false);
    for(int i=0;i<n;i++){
        int u=-1,minn=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&Time[j]<minn){
                u=j;
                minn=Time[j];
            }
        }
        if(u==-1) break;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&w[u][v]!=0){
                if(Time[u]+w[u][v]<Time[v]){
                    Time[v]=Time[u]+w[u][v];
                    Timepre[v]=u;
                    nodenum[v]=nodenum[u]+1;
                }else if(Time[u]+w[u][v]==Time[v]&&nodenum[u]+1<nodenum[v]){
                    Timepre[v]=u;
                    nodenum[v]=nodenum[u]+1;
                }
            }
        }
    }
    dfsTimepath(fin);
    printf("Distance = %d",dis[fin]);
    if(dispath==Timepath)
        printf("; Time = %d: ",Time[fin]);
    else{
        printf(": ");
        for(int i=dispath.size()-1;i>=0;i--){
            printf("%d",dispath[i]);
            if(i!=0) printf(" -> ");
        }
        printf("\nTime = %d: ",Time[fin]);
    }
    for(int i=Timepath.size()-1;i>=0;i--){
        printf("%d",Timepath[i]);
        if(i!=0) printf(" -> ");
    }
    return 0;
}