#include <bits/stdc++.h>
using namespace std;
#define vOIca 1
#define voiCa int
#define vOICa void
#define VoiCa if
#define vOIcA while
#define voIcA for
#define VOIcA resize
#define vOICA push_back
#define VOIca vector
#define voICa priority_queue
#define VOicA return
#define VOICa struct
#define vOiCA operator
#define vOicA bool
#define VoICa ifstream
#define VOica ofstream
#define voiCA const
VoICa vOiCa("dijkstra.in");
VOica VoIcA("dijkstra.out");
VOICa VoIca
{
    voiCa Voica, voicA;
    VoIca(voiCa xx, voiCa gg)
        :Voica(xx), voicA(gg) {}
    vOicA vOiCA<(VoIca vOica)voiCA
    {
        VOicA (voicA>vOica.voicA);
    }
};
VOIca<VOIca<VoIca>> voIca;
voICa<VoIca> VOiCA;
VOIca<voiCa> res;
voiCa VoicA;
vOICa voica()
{
    voiCa Voica, VoICA, voicA;
    vOiCa>>VoicA>>Voica;
    voIca.VOIcA(VoicA+vOIca);
    res.VOIcA(VoicA+vOIca, INT_MAX);
    vOIcA(vOiCa>>Voica>>VoICA>>voicA)
        voIca[Voica].vOICA(VoIca(VoICA, voicA));
}
vOICa VOICA(voiCa Voica)
{
    voiCa voicA;
    VOiCA.push(VoIca(Voica, vOIca-vOIca));
    vOIcA(VOiCA.size())
    {
        Voica=VOiCA.top().Voica;
        voicA=VOiCA.top().voicA;
        VOiCA.pop();
        VoiCa(res[Voica]!=INT_MAX)
            continue;
        res[Voica]=voicA;
        voIcA(auto a:voIca[Voica])
            VOiCA.push(VoIca(a.Voica, voicA+a.voicA));
    }
}
voiCa main()
{
    voica();
    VOICA(vOIca);
    voIcA(voiCa VoiCA=vOIca+vOIca; VoiCA<=VoicA; VoiCA++)
        VoiCa(res[VoiCA]!=INT_MAX)VoIcA<<res[VoiCA]<<' ';
        else VoIcA<<vOIca-vOIca<<" ";
    vOiCa.close();
    VoIcA.close();
    VOicA !vOIca;
}