/*
//Dijkstra:
// Folosim algoritmul lui Dijkstra pentru determinarea drumurilor minime de la un nod sursa 
// catre toate celelalte noduri din graf (orientat, aciclic, cu costuri strict pozitive).
// Ideea principala este sa mentinem, pentru fiecare nod, costul minim cunoscut pana la acel moment 
// de a ajunge la el din sursa, actualizand aceste valori de fiecare data cand gasim un drum mai ieftin.

//1. Initializare
//Setam distanta pentru nodul sursa la 0, iar pentru toate celelalte noduri la infinit.
//In coada de prioritati vom insera o pereche, pe prima pozitie se va afla distanta actuala a nodului, iar pe a doua pozitie se va afla un numar care reprezinta nodul.

//2. Procesarea fiecarui nod
//Extragem din coada de prioritati nodul cu distanta cea mai mica (operatie cu cost O(log N)).
//Consideram distanta acestui nod ca fiind determinata definitiv (nu exista costuri negative, 
//deci nu va mai aparea un drum mai ieftin pentru acest nod ulterior).
//Pentru fiecare nod adiacent, incercam sa relaxam muchia (verificam daca putem obtine 
//o distanta mai mica prin intermediul nodului curent). Daca da, actualizam distanta 
//si inseram/actualizam nodul vecin in coada de prioritati.

// Complexitatea este: O(M log N). 
// Acest lucru se datoreaza faptului ca la fiecare extragere din coada (operatie O(log N)), 
// putem avea actualizari ale distantelor pe fiecare muchie si, implicit, inserari/actualizari 
// in coada (fiecare in O(log N)). Cum fiecare muchie este procesata cel mult o data 
// in mod semnificativ (la relaxare), rezulta O(M log N) in total.

#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int inf=1e9;
vector<vector<pair<int,int>>>gr;
vector<int>distanta;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>q;

void dijkstra(int nod){
    distanta[nod]=0;
    q.push({distanta[nod],nod});

   pair<int,int> nod_curent;

    while(!q.empty()){

        nod_curent=q.top();
        q.pop();

        if(nod_curent.first!=distanta[nod_curent.second]){
            continue;
        }

        for(const auto&nod:gr[nod_curent.second]){
            if(distanta[nod_curent.second]+nod.second<distanta[nod.first]){

                distanta[nod.first]=distanta[nod_curent.second]+nod.second;

                q.push({distanta[nod.first],nod.first});
            }
        }
    }
}
int main(){

    int n,m,nod1,nod2,cost;
    cin>>n>>m;

    gr.resize(n+1);
    distanta.resize(n+1,inf);

    for(int i=1;i<=m;i++){
        cin>>nod1>>nod2>>cost;
        gr[nod1].push_back({nod2,cost});
    }

    dijkstra(1);

    for(int i=2;i<=n;i++){
        if(distanta[i]==inf){
            cout<<0<<" ";
        }else{
            cout<<distanta[i]<<" ";
        }
    }   
}
*/
/*
//Pentru a determina fortareata corespunzatoare catunelor
//aplic algoritmul lui Dijkstra din toate fortaretele (multisource)
//Astfel aflu pentru fiecare catun fortareta de la care distanta este minima
//Daca un catun are distanta egala la doua (sau mai multe) fortarete,
//atunci il asociez fortaretei cu indicele cel mai mic
//Dijkstra multisource rezolva si cazul in care graful nu este conex
//Complexitatea finala este O(M * logN)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream cin("catun.in");
ofstream cout("catun.out");

const int inf=1e9;
vector<int>fortareata,distanta;
vector<vector<pair<int,int>>>gr;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>q;

void dijkstra(){

    while(!q.empty()){

        pair<int,int>nod_curent=q.top();
        q.pop();

        if(nod_curent.first!=distanta[nod_curent.second]){
            continue;
        }

        for(const auto&nod:gr[nod_curent.second]){

            if(distanta[nod_curent.second]+nod.second<distanta[nod.first]){

                distanta[nod.first]=distanta[nod_curent.second]+nod.second;
                fortareata[nod.first]=fortareata[nod_curent.second];

                q.push({distanta[nod.first],nod.first});

            }else if(distanta[nod_curent.second]+nod.second==distanta[nod.first] && fortareata[nod.first]>fortareata[nod_curent.second]){
                
                fortareata[nod.first]=fortareata[nod_curent.second];

                q.push({distanta[nod.first],nod.first});
            }
        }
    }
}
int main(){
    int n,m,k,nod,nod1,nod2,cost;
    cin>>n>>m>>k;
    fortareata.resize(n+1,-1);
    distanta.resize(n+1,inf);
    gr.resize(n+1);

    for(int i=1;i<=k;i++){
        cin>>nod;
        fortareata[nod]=nod;
        distanta[nod]=0;
        q.push({0,nod});
    }
    for(int i=1;i<=m;i++){
        cin>>nod1>>nod2>>cost;
        gr[nod1].push_back({nod2,cost});
        gr[nod2].push_back({nod1,cost});
    }
    dijkstra();

    for(int i=1;i<=n;i++){
        if(fortareata[i]==i || distanta[i]==inf){
            cout<<0<<" ";
        }else{
            cout<<fortareata[i]<<" ";
        }
    }
}
*/
//Bellman Ford
/*
//O(M*N)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

queue<int>q;
vector<int>folosit,distanta,vizitat;
vector<vector<pair<int,int>>>gr;

const int inf=1e9;

int n,m,nod1,nod2,cost;

void bellmanford(int nod){
    distanta[nod]=0;
    q.push(nod);
    folosit[nod]=1;

    while(!q.empty()){
        int nod_curent=q.front();
        q.pop();
        folosit[nod_curent]=0;
        vizitat[nod_curent]++;

        if(vizitat[nod_curent]>n){
            cout<<"Ciclu negativ!";
            exit(0);
        }

        for(const auto&nod_vecin:gr[nod_curent]){
            if(distanta[nod_curent]+nod_vecin.second<distanta[nod_vecin.first]){
                distanta[nod_vecin.first]=distanta[nod_curent]+nod_vecin.second;

                if(!folosit[nod_vecin.first]){
                    q.push(nod_vecin.first);
                    folosit[nod_vecin.first]=1;
                }else{
                vizitat[nod_vecin.first]++;//pentru a putea prinde un ciclu negativ ,am gasit un drum mai bun ,iar nodul in care ma aflu este pe coada
                }
            }
        }
    }
    for(int i=2;i<=n;i++){
        cout<<distanta[i]<<" ";
    }
}

int main(){
    cin>>n>>m;
    gr.resize(n+1);
    distanta.resize(n+1,inf);
    folosit.resize(n+1,0);
    vizitat.resize(n+1,0);

    for(int i=1;i<=m;i++){
        cin>>nod1>>nod2>>cost;
        gr[nod1].push_back({nod2,cost});
    }
    bellmanford(1);
     
}
*/
//Floyd Warshall
//O(N^3)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("royfloyd.in");
ofstream cout("royfloyd.out");
vector<vector<int>>mat;
const int inf=1e9;
int main(){
    int n;
    cin>>n;
    mat.resize(n+1,vector<int>(n+1));

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>mat[i][j];
            if(mat[i][j]==0){
                mat[i][j]=inf;
            }
        }
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            if(k==i || mat[i][k]==inf){
                continue;
            }
            for(int j=1;j<=n;j++){
                if(j==k || i==j || mat[k][j]==inf){
                    continue;
                }
             mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);//doar nodurile intermediare trebuie sa fie intre [1,k]
             //nu capetele (de extremitate)
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mat[i][j]==inf){
                mat[i][j]=0;
            }
            cout<<mat[i][j]<<" ";
        }
        cout<<'\n';
    }
}



#include <iostream>
#include <queue>
#include <vector>
using namespace std;
//ifstream cin("maxflow.in");
//ofstream cout("maxflow.out");
queue<int>q;
vector<vector<int>>flux,gr,capacitate;
vector<int>tata;

int n,m,nod1,nod2,cap,S,T,rasp=0;
const int inf=1e9;

int bfs(){
    int val=0;

    for(int i=1;i<=n;i++){
        tata[i]=0;
    }
    tata[S]=S;
    q.push(S);

    //aici imi caut drumul pe care o sa vad daca pot sa mai trimit flux ,respectiv daca trebuie sa redirectionez
    while(!q.empty()){

        int nod_curent=q.front();
        q.pop();

        if(nod_curent==T){
            //am gasit cel putin un drum nesaturat 
            continue;
        }
        for(auto&vecin:gr[nod_curent]){

            if(!tata[vecin] && capacitate[nod_curent][vecin]-flux[nod_curent][vecin]>0){
                tata[vecin]=nod_curent;
                q.push(vecin);
            }
        }
    }

        //cat timp exista lant nesaturat de la s la t,verific daca mai pot trimite flux,respectiv daca pot redirectiona
        for(auto& vecin:gr[T]){//ma uit in toate nodurile care sunt adiacente cu destinatia,deoarece prin ele 
        //vor trece drumurile cu fluxul adaugat
             if(!tata[vecin]){
                continue;
             }
             tata[T]=vecin;
             int nod_curent=T;
             int minn=inf;

             while(nod_curent!=S){
                minn=min(minn,capacitate[tata[nod_curent]][nod_curent]-flux[tata[nod_curent]][nod_curent]);
                nod_curent=tata[nod_curent];
             }
             nod_curent=T;

             while(nod_curent!=S){
                flux[tata[nod_curent]][nod_curent]+=minn;
                flux[nod_curent][tata[nod_curent]]-=minn;
                nod_curent=tata[nod_curent];
             }
             val+=minn;
        }        

    return val;
}
int main(){

    cin>>n>>m;

    S=1;
    T=n;

    gr.resize(n+1);
    tata.resize(n+1,0);
    capacitate.resize(n+1,vector<int>(n+1));
    flux.resize(n+1,vector<int>(n+1));

    for(int i=1;i<=m;i++){
        cin>>nod1>>nod2>>cap;

        gr[nod1].push_back(nod2);
        gr[nod2].push_back(nod1);
        capacitate[nod1][nod2]=cap;
    }

    int flx;

    bool ok=true;
    while(ok){
        flx=bfs();
        if(flx==0){
            ok=false;
        }
        rasp+=flx;
    }
    cout<<rasp;
    return 0;
}