//toate permutarile ale elementelor impare
// Atilla si regele : un cal si un rege se afla pe o tabla de sah. UNele campuri sunt arse. Pozitiile lor sunt cunoscute . Calul nu poate calca pe campurile arse iar orice miscare a calcului face ca respectivul camp sa fie ars. Aflati daca exista o succesiune de mutari permise prin care calul sa ajung ala rege si sa refina pe pozitia initiala .Pozitia calului si pozitia regelui sunt considerate nearse
#include<fstream>
#define M 2000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
/*ifstream f("date.in");
ofstream g("date.out");*/

struct nod
{
    int inf;
    int c;
    nod * leg;
};
typedef nod* PNod;
PNod L[50001];
int q[800000],cost[50001],n,m,nr[50001];
void add(int a,int b,int costi)
{
    PNod p=new nod;
    p->inf=b;
    p->c=costi;
    p->leg=L[a];
    L[a]=p;
}
void bellford()
{

     int inc=1,sf=1,i;nr[1]++;
    while(inc<=sf)
    {
        for(PNod p=L[q[inc]];p;p=p->leg)
            if(cost[p->inf]>cost[q[inc]]+p->c)
            {
                cost[p->inf]=cost[q[inc]]+p->c;
                sf++;
                q[sf]=p->inf;nr[p->inf]++;
            }
        inc++;
    }

        for(i=2;i<=n;i++)
            if(cost[i]!=M)
                g<<cost[i]<<" ";
                else g<<"0 ";

}
int main()
{
    int a,b,costi,i;
    f>>n>>m;
    for(i=1;i<=m;i++)
      {
           f>>a>>b>>costi;
        add(a,b,costi);
      }
        for(i=2;i<=n;i++)
            cost[i]=M;
    q[1]=1;
    bellford();
    return 0;
}