#include<iostream>
#include<iomanip>
#include<queue>
#include<string>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#include<vector>
#include<functional>

using namespace std;

typedef  long long           ll;
typedef  unsigned            ui;
typedef  unsigned long long  ull;
typedef  pair<int,int>       i_i;
typedef  pair<ll,int>        ll_i;
typedef  pair<ll,ll>         ll_ll;
typedef  pair<double,int>    d_i;
typedef  pair<double,double> d_d;

#ifdef DEBUG
#define dprintf      printf
#define dputs        puts
#define dout(x)      cout<<#x" = "<<(x)<<endl
#define darray(x,n)  {int i;rep(i,n)cout<<#x"["<<i<<"] = "<<*((x)+i)<<endl;}
#define dloop(i,s,g) for(int (i)=(s);(i)<(g);(i)++)
#define drep(i,n)    for(int (i)=0;(i)<(n);(i)++)
#define dstop()      scanf("%*c")
#else
#define dprintf      (1)?0:printf
#define dputs        (1)?0:puts
#define dout(x)
#define darray(x,n)
#define dloop(i,s,g) if(int i=0){}else
#define drep(i,n)    if(int i=0){}else
#define dstop()
#endif

#define F    first
#define S    second
#define pb   push_back
#define mp   make_pair

#define loop(i,s,g) for((i)=(s);(i)<(g);(i)++)
#define rep(i,n)    for((i)=0;(i)<(n);(i)++)
#define all(x)      (x.begin(),x.end())
#define in(T,...) T __VA_ARGS__; impl(__VA_ARGS__)
#define array(T,id,n) T id[(n)]; for(int i=0;i<(n);i++)cin>>id[i]
#define putv(n)     cout<<(n)<<endl

//#define int long long;
#ifndef int
#define INF (0x7fffffff)
#else
#define INF (0x7fffffffffffffff)
#endif

void impl(){};
template <typename T,typename... TS >
void impl(T &head,TS &... tail)
{
  cin>>head;
  impl(tail ...);
}

#define MAX_V 112345

struct edge
{
  int to;
  int cap;
  int cost;
  int rev;
};

int V; // ????????°
vector<edge> G[MAX_V]; // ??°???????????£??\???????????¨???
int d[MAX_V]; // ???????????¢
int prevv[MAX_V],preve[MAX_V]; // ??´??????????????¨???

// from??????to????????????cap????????????????????? 
void add_edge(int from,int to,int cap,int cost)
{
  G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
  G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
}

// s??????t????????????f???????°??????¨???????±???????(??????????????´??????-1)
int min_cost_flow(int s,int t,int f)
{
  int res=0;
  while(f>0)
    {
      fill(d,d+V,INF);
      d[s]=0;
      bool update=true;
      while(update)
	{
	  update=false;
	  for(int v=0;v<V;v++)
	    {
	      if(d[v]==INF)
		continue;
	      for(int i=0;i<(int)G[v].size();i++)
		{
		  edge &e=G[v][i];
		  if(e.cap>0&&d[e.to]>d[v]+e.cost)
		    {
		      d[e.to]=d[v]+e.cost;
		      prevv[e.to]=v;
		      preve[e.to]=i;
		      update=true;
		    }
		}
	    }
	}
      if(d[t]==INF)
	return -1;
      
      int dc=f;
      for(int v=t;v!=s;v=prevv[v])
	dc=min(dc,G[prevv[v]][preve[v]].cap);

      f-=dc;
      res+=dc*d[t];

      for(int v=t;v!=s;v=prevv[v])
	{
	  edge &e=G[prevv[v]][preve[v]];
	  e.cap-=dc;
	  G[v][e.rev].cap+=dc;
	}
    }
  return res;
}

signed main(void)
{
  cin>>V;
  in(int,e,f);
  int from,to,cap,cost;
  int i;
  rep(i,e)
    {
      cin>>from>>to>>cap>>cost;
      add_edge(from,to,cap,cost);
    }

  cout<<min_cost_flow(0,V-1,f)<<endl;
  return 0;
}

Measured memory_bytes: 5840