#include<iostream>
#include<string>
#include<algorithm>
#define endl '\n'
using namespace std;
using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,s,t;
ll ans,fs[300005],ft[300005];
string anss;
struct eg{int u,v,w;}a[300005];
int main(){
    cin>>n>>s>>t;
    for(int i=1;i<n;i++) cin>>a[i].u>>a[i].v>>a[i].w;
    
    if(s>t) swap(s,t);
    ll sum=0;
    for(int i=1;i<s;i++) sum+=a[i].w,ans+=sum,anss+='1';
    for(int i=s;i<t;i++) fs[i]=fs[i-1]+a[i].w;
    for(int i=t-1;i>=s;i--) ft[i]=ft[i+1]+a[i].w;
    int mid=t;
    for(int i=s;i<t;i++) if(fs[i]>ft[i]){mid=i; break;}
    for(int i=s;i<mid-1;i++) ans+=fs[i],anss+='2';
    anss+='0';
    for(int i=mid;i<t;i++) ans+=ft[i],anss+='1';
    sum=0;
    for(int i=n-1;i>=t;i--) sum+=a[i].w,ans+=sum,anss+='2';
    cout<<ans<<endl<<anss<<endl;
    
    return 0;
}

思路：st 两侧的都往 st 连，中间的哪边近连哪边。

https://www.luogu.com.cn/record/227554625