#include <iostream>
using namespace std;
int dfs(int s[][300],int x,int y);
int max_int=999999;
int main()
{
    int n;
    while(cin>>n&&n)
    {
        int s[300][300]= {{0}},i,a,b,c,p=0,min,sum,k;
        for(i=0; i<n; i++)
        {
            cin>>a>>b>>c;
            s[a][b]=c;
            s[b][a]=c;
            if(b>p)
                p=b;
        }
        for(i=0; i<=p; i++)
        {
            sum=dfs(s,i,p);
            cout<<sum<<endl;
            if(i==0)
                min=sum,k=0;
            else if(sum<min)
                min=sum,k=i;
        }
        cout<<k<<" "<<min<<endl;
    }
    return 0;
}
int dfs(int s[][300],int x,int y)
{
    bool s0[300];
    int i,j,sum=0,dist[300]= {max_int};
    for(i=0; i<=y; ++i)
    {
        if(s[x][i])
            dist[i]=s[x][i];
        else
            dist[i]=max_int;
        s0[i]=0;
    }
    dist[x]=0;
    s0[x]=1;
    for(i=1; i<=y; ++i)
    {
        int tmp =max_int;
        int u = x;
        for(j=0; j<=y; ++j)
            if((!s0[j]) && dist[j]<tmp)
            {
                u = j;
                tmp = dist[j];
            }
        s0[u] = 1;
        for(j=0; j<=y; ++j)
            if((!s0[j]) && s[u][j]&& s[u][j]<max_int)
            {
                int newdist = dist[u] + s[u][j];
                if(newdist < dist[j])
                    dist[j] = newdist;
            }
    }
    for(i=0; i<=y; i++)
    {
        if(dist[i]<max_int)
            sum+=dist[i];
    }
    return sum;
}