// O(N^2 * M^2)
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define Nmax 355
#define oo 2000000000
#define pb push_back
using namespace std;
ifstream f("fmcm.in");
ofstream g("fmcm.out");

int N,M,Source,Sink,x,y,c,z,MaxFlow,CostMin,used[Nmax];
int cap[Nmax][Nmax],cost[Nmax][Nmax],flow[Nmax][Nmax],ante[Nmax],d[Nmax];
vector < int > G[Nmax];
bitset < Nmax > inQ,viz,calc[Nmax];
queue < int > Q;
struct cmp
{
    bool operator()(const int &a,const int &b)const
    {
        return d[a]>d[b];
    }
};
priority_queue < int  , vector < int > , cmp > pq;
inline void ReadInput()
{
    f>>N>>M>>Source>>Sink;
    for(int i=1;i<=M;++i)
        {
            f>>x>>y>>c>>z;
            z+=oo/2;
            G[x].pb(y) , G[y].pb(x);
            cap[x][y]=c;
            cost[x][y]=z , cost[y][x]=-z;
        }
}

int BF(int Source)
{
    for(int i=1;i<=N;++i)d[i]=oo,ante[i]=oo,used[i]=0;
    d[Source]=0 , ante[Source]=Source ,  inQ[Source]=1;
    for(Q.push(Source); !Q.empty();Q.pop())
    {
        int node=Q.front();
        inQ[node]=0; ++used[node];
        if(used[node]==N)return 0;
        for(vector<int>::iterator it=G[node].begin();it!=G[node].end();++it)
            if(d[*it]>d[node]+cost[node][*it] && flow[node][*it]<cap[node][*it])
            {
                d[*it]=d[node]+cost[node][*it];
                ante[*it]=node;
                if(!inQ[*it])Q.push(*it) , inQ[*it]=1;
            }
    }
    return 1;
}

inline void DFS(int node)
{
    for(vector<int>::iterator it=G[node].begin();it!=G[node].end();++it)
        if(cap[node][*it]>0 && !calc[node][*it])
        {
            g<<node<<' '<<*it<<'\n';
            calc[node][*it]=1;
            z=cost[node][*it]+d[node]-d[*it];
            cost[node][*it]=z;
            cost[*it][node]=-z;
            DFS(*it);
        }
}


int Dijkstra(int Source)
{
    for(int i=1;i<=N;++i)d[i]=oo,ante[i]=oo;
    d[Source]=0 , ante[Source]=Source;
    for(pq.push(Source); !pq.empty(); pq.pop())
    {
        int node=pq.top();
        for(vector<int>::iterator it=G[node].begin();it!=G[node].end();++it)
            if(d[*it]>d[node]+cost[node][*it])
            {
                d[*it]=d[node]+cost[node][*it];
                ante[*it]=node;
                pq.push(*it);
            }
    }
    for(int i=1;i<=N;++i)g<<d[i]<<' ';g<<'\n';
    if(d[Sink]!=oo)
    {
        int MinFlow=oo;
        for(int i=Sink; i!=Source ; i=ante[i])
            MinFlow=min(MinFlow,cap[ante[i]][i]-flow[ante[i]][i]);
        if(MinFlow)
        {
            for(int i=Sink; i!=Source ; i=ante[i])
            {
                flow[ante[i]][i]+=MinFlow;
                flow[i][ante[i]]-=MinFlow;
            }
            return MinFlow;
        }
    }
    return 0;

}
int main()
{
    ReadInput();
    BF(Source);
    for(int i=1;i<=N;++i)g<<d[i]<<' ';g<<'\n';

    DFS(Source);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=N;++j)
            if(cap[i][j]>0)g<<i<<' '<<j<<' '<<cost[i][j]<<'\n';
    for(int MinFlow=Dijkstra(Source); MinFlow ; MinFlow=Dijkstra(Source) )
        CostMin+=MinFlow*d[Sink] ;// , MaxFlow+=MinFlow;
    g<<CostMin<<'\n';
    f.close();g.close();
    return 0;
}