#include<bits/stdc++.h>

using namespace std;
int n,m,r;
struct edge{
    int u,v,w;
}e[400005];
struct Heap{
    int lson,rson;
    int len;
    long long val,tag;
    int fr,id;
}t[400005];
int root[400005];
int g;
int Newnode(long long val,int fr,int id){
    t[++g]={0,0,1,val,0,fr,id};
    return g;
}
void pu(int rt,long long val){
    if(!rt)return;
    t[rt].tag+=val;
    t[rt].val+=val;
}
void pushdown(int rt){
    if(t[rt].tag==0)return;
    pu(t[rt].lson,t[rt].tag);
    pu(t[rt].rson,t[rt].tag);
    t[rt].tag=0;
}
void merge(int &rt,int x,int y){
    if(!x||!y){
        rt=x+y;
        return;
    }
    if(t[x].val>t[y].val)swap(x,y);
    rt=x;pushdown(x);
    merge(t[rt].rson,t[x].rson,y);
    if(t[t[rt].rson].len>t[t[rt].lson].len)swap(t[rt].lson,t[rt].rson);
    t[rt].len=t[t[rt].rson].len+1;
}
long long ans=0;
int fa[400005],fa2[400005],cnt;
bool pd[400005];
int Find(int u){
    return (fa[u]==u?u:(fa[u]=Find(fa[u])));
}
int Find2(int u){
    return (fa2[u]==u?u:(fa2[u]=Find2(fa2[u])));
}
stack<int>st;
int Fa[400005];
int Tarjan(int u){
    cnt++;
    while(!st.empty()){
        int v=st.top();st.pop();
        merge(root[cnt],root[cnt],root[v]);
        fa2[v]=cnt;Fa[v]=cnt;
        if(v==u)break;
    }
    if(!st.empty()){
        int f1=Find(st.top());
        fa[cnt]=f1;
    }
    return cnt;
}
int fr[400005];
int lans[400005];
vector<int>son[200005];
void Solve(int u){
    if(pd[u])return;
    st.push(u);pd[u]=true;
    int v=Find2(t[root[u]].fr);
    while(u==v){
        pushdown(root[u]);
        merge(root[u],t[root[u]].lson,t[root[u]].rson);
        v=Find2(t[root[u]].fr);
    }
    fr[u]=t[root[u]].id;
    long long d=t[root[u]].val;
    ans+=d;pushdown(root[u]);
    merge(root[u],t[root[u]].lson,t[root[u]].rson);
    pu(root[u],-d);
    int f1=Find(u),f2=Find(v);
    if(f1!=f2){
        fa[f1]=f2;
        Solve(v);
    }
    else Solve(Tarjan(v));
}
bool chk[200005];
void del(int u){
    if(chk[u])return;
    chk[u]=true;del(Fa[u]);
}
int main(){
    scanf("%d%d%d",&n,&m,&r);r++;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);u++;v++;e[i]={u,v,w};
        merge(root[v],root[v],Newnode(w,u,i));
    }
    for(int i=2;i<=n;i++)
        merge(root[i],root[i],Newnode(1e18,i-1,0));
    merge(root[1],root[1],Newnode(1e18,n,0));
    for(int i=1;i<=n*2;i++)fa[i]=i,fa2[i]=i,Fa[i]=i;pd[r]=true;
    cnt=n;
    for(int i=1;i<=n;i++){
        while(!st.empty())st.pop();
        Solve(i);
    }
    printf("%lld\n",ans);
    for(int i=cnt;i>=1;i--){
        if(!chk[i]&&i!=r){
            lans[e[fr[i]].v]=e[fr[i]].u;
            del(e[fr[i]].v);
        }
    }
    lans[r]=r;
    for(int i=1;i<=n;i++)printf("%d ",lans[i]-1);
    return 0;
}