#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAX 10000

#define fr(a,b,c) for(int a = b ; a < c ; a++ )
#define rp(a,c) fr(a,0,c)


using namespace std;

int pos;
int inicio,fim;
int v,arestas;
int matriz[MAX][2*MAX];
int vet[MAX];
bool vis[MAX];


struct ligado
{
    int a;
    int pos;
    ligado(int a = 0, int pos = 0): a(a), pos(pos){}

}aux2[MAX];

struct ponto
{
    int x;
    int y;
    int c;
    int pos;

    ponto(int x=0, int y = 0, int c = 0, int pos = 0): x(x), y(y), c(c), pos(pos){}

}aux[10000];


bool minimo(ponto a, ponto b)
{
    if(a.c < b.c) return true;
    else return false;
}

void heap_push(ponto novo)
{
    pos++;
    aux[pos] = novo;
    int n = pos;
    bool troca = true;
    ponto aux2;
    int pai = n/2;

    while(n>1 && troca)
    {
        troca = false;
        if(aux[n].c <= aux[pai].c)
        {
            aux2 = aux[pai];
            aux[pai] = aux[n];
            aux[n]=aux2;
            troca=true;
        }
        n = pai;
        pai = n/2;
    }

}

void heap_pop()
{
    aux[1]=aux[pos];
    pos--;

    int n = pos;

    int i=1;
    ponto aux2;
    int menor;

    while(i <= n/2)
    {
        if(i< (n/2 + n%2))
        {
            if(aux[2*i].c < aux[2*i +1].c)
            {
                menor = 2*i;
            }
            else
            {
                menor = 2*i +1;
            }
        }
        else
        {
            menor = 2*i;
        }


        if(aux[i].c > aux[menor].c)
        {
            aux2 = aux[i];
            aux[i] = aux[menor];
            aux[menor] = aux2;

            i = menor;
        }
        else
        {
            i = n;
        }
    }


}

int process()
{
    pos=0;

    rp(i,vet[inicio])
    {
        int ant = inicio;
        int prox = matriz[inicio][i];
        i++;
        int c = matriz[inicio][i];
        heap_push(ponto(ant,prox,c,i));
    }

    vis[inicio] = true;


    while(pos)
    {
        int ant = aux[1].x;
        int atual = aux[1].y;
        int c = aux[1].c;
        int pos = aux[1].pos;

        heap_pop();

        if(atual == fim)
        {
             aux2[atual] = ligado(ant,pos);
             return c;
        }

        if(!vis[atual])
        {
            vis[atual] = true;

            aux2[atual] = ligado(ant,pos);

            rp(i,vet[atual])
            {
                int prox = matriz[atual][i];
                i++;
                int custo = matriz[atual][i];

                if(!vis[prox])
                {
                    heap_push(ponto(atual,prox,c + custo,i));
                }
            }
        }
    }


    return -1;
}

int process2()
{
    pos=0;

    rp(i,vet[fim])
    {
        int ant = fim;
        int prox = matriz[fim][i];
        i++;
        int c = matriz[fim][i];
        heap_push(ponto(ant,prox,c,0));
        heap_push(ponto(ant,prox,c/2,1));
    }

    vis[fim] = true;

    while(pos)
    {
        int atual = aux[1].y;
        int c = aux[1].c;
        int bic = aux[1].pos;

        heap_pop();

        if(atual == inicio) return c;

        if(!vis[atual])
        {
            vis[atual] = true;

            rp(i,vet[atual])
            {
                int prox = matriz[atual][i];
                i++;
                int custo = matriz[atual][i];

                if(!vis[prox])
                {
                    heap_push(ponto(atual,prox,c + custo,0));

                    if(!bic)
                    {
                        heap_push(ponto(atual,prox,c + custo/2,1));
                    }

                }
            }
        }
        else
        {
            if(!bic)
            {
                rp(i,vet[atual])
                {
                    int prox = matriz[atual][i];
                    i++;
                    int custo = matriz[atual][i];

                    if(!vis[prox])
                    {
                        heap_push(ponto(atual,prox,c + custo/2,1));
                    }
                }
            }
        }


    }


    return -1;


}


void removeArestas()
{
    int remover = fim;

    while(aux2[remover].a != inicio)
    {
        int a = aux2[remover].a;
        int pos = aux2[remover].pos;

        vet[a] = vet[a] - 2;

        matriz[a][pos] = matriz[a][vet[a]];
        matriz[a][pos+1] = matriz[a][vet[a]+1];

        remover = a;
    }


}


int main()
{
    freopen("L4Q4.in","r",stdin);
    int caso=1;
    while(scanf("%d %d",&v,&arestas)>0 && (v!=0 || arestas!=0))
    {

        memset(vet,0,sizeof(vet));
        memset(vis,false,sizeof(vis));

        scanf("%d %d",&inicio,&fim);

        rp(i,arestas)
        {
            int x,y,c;

            scanf("%d %d %d",&x,&y,&c);
            matriz[x][vet[x]] = y;
            vet[x]++;
            matriz[x][vet[x]] = c;
            vet[x]++;
        }

        if(inicio == fim)
        {
             printf("Caso #%d: %d\n",caso++,-1);
             printf("-1\n");
             continue;
        }

        int retorno = process();

        printf("Caso #%d: %d\n",caso++,retorno);

        if(retorno > 0)
        {
            removeArestas();
            memset(vis,false,sizeof(vis));

            printf("%d\n",process2());

        }
        else
        {
            printf("-1\n");
        }


    }
    return 0;
}