#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>

using namespace std;
#define nmax 50000

int c[nmax],heap[nmax],viz[nmax],poz[nmax],dim;

void heapify(int i)
{
    if (2*i+1<=dim && c[heap[i]]>c[heap[i*2+1]])
    {
        int aux=heap[i];
        heap[i]=heap[i*2+1];
        heap[i*2+1]=aux;
        aux=poz[i];
        poz[i]=poz[i*2+1];
        poz[i*2+1]=aux;
        heapify(2*i+1);
    }
        else if (2*i+2<=dim && c[heap[i]]>c[heap[i*2+2]])
        {
            int aux=heap[i];
            heap[i]=heap[2*i+2];
            heap[2*i+2]=aux;
            aux=poz[i];
            poz[i]=poz[i*2+2];
            poz[i*2+2]=aux;
            heapify(2*i+2);
        }
}

void reverseheapify(int i)
{
    if (i>0 && c[heap[i]]<c[heap[i/2]])
        {
            int aux=heap[i];
            heap[i]=heap[i/2];
            heap[i/2]=aux;
            aux=poz[i];
            poz[i]=poz[i/2];
            poz[i/2]=aux;
            reverseheapify(i/2);
        }
}

int decapitare()
{
    int u=heap[0];
    heap[0]=heap[dim];
    heap[dim]=u;
    dim--;
    heapify(0);
    poz[u]=-1;
    return u;
}

int main()
{
    int n,m,a,b,cost,nr=1;
    ifstream f("dijkstra.in");
    f>>n>>m;
    vector<pair<int,int> > v[n+1];
    for (int i=0;i<m;i++)
    {
        f>>a>>b>>cost;
        v[a].push_back(make_pair(b,cost));
    }
    for (int i=2;i<=n;i++)
    {
        c[i]=INT_MAX;
        viz[i]=0;
        poz[i]=-1;
    }
    c[1]=0;
    dim=-1;
    viz[1]=1;
    for (int i=0;i<v[1].size();i++)
    {
        c[v[1][i].first]=v[1][i].second;
        heap[++dim]=v[1][i].first;
        reverseheapify(dim);
        poz[v[1][i].first]=dim;
        viz[v[1][i].first]=1;
    }
    for (int i=0;i<=dim;i++) cout<<heap[i]<<" ";
    while (dim>=0)
    {
        int u=decapitare();
        cout<<"pasul"<<nr<<endl;
        for (int i=0;i<=dim;i++) cout<<heap[i]<<" ";
        cout<<endl;
        for (int i=1;i<=n;i++) cout<<c[i]<<" ";
        for (int i=0;i<v[u].size();i++)
            if (v[u][i].second+c[u]<c[v[u][i].first])
            {
                c[v[u][i].first]=v[u][i].second+c[u];
                if (poz[v[u][i].first]==-1)
                {
                    heap[++dim]=v[u][i].first;
                    reverseheapify(dim);
                    viz[v[u][i].first]=1;
                }
                    else reverseheapify(poz[v[u][i].first]);
            }
        cout<<endl<<"pasul"<<nr<<endl;
        for (int i=0;i<=dim;i++) cout<<heap[i]<<" ";
        cout<<endl;
        for (int i=1;i<=n;i++) cout<<c[i]<<" ";
        nr++;
    }
    for (int i=2;i<=n;i++) if (c[i]==INT_MAX) c[i]=0;
    ofstream g("dijkstra.out");
    for (int i=2;i<=n;i++) g<<c[i]<<" ";
    return 0;
}