#include <bits/stdc++.h>
#define N 400
#define INF 0x3f3f3f3f
using namespace std;
ifstream fin("fmcm.in");
ofstream fout("fmcm.out");
struct muchie
{
    int x,y,f,c;
};
vector<int>g[N];
bool viz[N];
int n,m,s,t,maxFlow;
int nivel[N],last[N];
long long minCost;
int d[N],dp[N],D[N],tata[N];
queue<int>q;
vector<muchie>edges;
void BellmanFord()
{
    d[s]=0;
    q.push(s);
    viz[s]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        viz[x]=0;
        for(auto i:g[x])
            if(edges[i].f && d[edges[i].y]>d[x]+edges[i].c)
        {
            int y=edges[i].y;
            d[y]=d[x]+edges[i].c;
            if(!viz[y]) viz[y]=1,q.push(y);
        }
    }
}
int dfs(int x,int minFlow)
{
    if(!minFlow) return 0;cout<<x<<" ";
    if(x==t) return minFlow;
    for(int &poz=last[x];poz<g[x].size();++poz)
    {
        int i=g[x][poz];
        int y=edges[i].y;
        int flux=edges[i].f;
        if(nivel[y]!=nivel[x]+1 || !flux) continue;
        int minFlow=dfs(y,min(minFlow,flux));
        if(!minFlow) continue;
        //edges[i].f-=minFlow;
        //edges[i^1].f+=minFlow;
        return minFlow;
    }
    return 0;
}
void dfs2(int x,int minFlow)
{
    if(x==t) return;
    for(int &poz=last[x];poz<g[x].size();++poz)
    {
        int i=g[x][poz];
        int y=edges[i].y;
        int flux=edges[i].f;
        if(nivel[y]!=nivel[x]+1 || !flux) continue;
        edges[i].f-=minFlow;
        edges[i^1].f+=minFlow;
        dfs(y,minFlow);
    }

}
struct myqueue
{
    int nod,cost;
    bool operator < (const myqueue x) const
    {
        return x.cost<cost;
    }
};
priority_queue<myqueue>pq;
bool Dijkstra()
{
    memset(dp,INF,sizeof(dp));
    dp[s]=D[s]=0;
    pq.push({s,0});
    while(!pq.empty())
    {
        int x=pq.top().nod;
        int z=pq.top().cost;
        pq.pop();
        if(z!=dp[x]) continue;
        for(auto i:g[x])
        {
            int flux=edges[i].f,cost=edges[i].c,y=edges[i].y;
            if(!flux) continue;
            int newCost=z+cost+d[x]-d[y];
            if(newCost<dp[y])
            {
                dp[y]=newCost;
                D[y]=D[x]+cost;
                ///tata[x]=nod;
                nivel[y]=nivel[x]+1;
                if(y!=t) pq.push({y,newCost});
            }
        }
    }
    if(dp[t]==INF) return 0;
    memcpy(d,D,sizeof(d));
    int minFlow=dfs(s,INF);
    if(!minFlow) return 0;
    maxFlow+=minFlow;
    minCost+=1ll*minFlow*D[t];
    dfs2(s,minFlow);
    return 1;
}
pair<int,long long>FMCM()
{
    BellmanFord();
    while(Dijkstra());
    return {maxFlow,minCost};
}
int main()
{
    int i,x,y,f,c;
    fin>>n>>m>>s>>t;
    for(i=0;i<m;i++)
        fin>>x>>y>>f>>c,
        g[x].push_back(2*i),
        edges.push_back({x,y,f,c}),
        g[y].push_back(2*i+1),
        edges.push_back({y,x,0,-c});
    fout<<FMCM().second;
    return 0;
}