#include<fstream>
#include<vector>
using namespace std;
vector<unsigned int> t[50001],c[50001],van;
int main()
{

    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    long i,a,b,d,s[50001],n,m,mi,vandb=1;
    f>>n>>m;
    for(i=2;i<=n;i++)
        s[i]=-1;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>d;
        t[a].push_back(b);
        c[a].push_back(d);
    }
    s[1]=0;
    vector<unsigned int>:: iterator iv,it,ic,pv,pt,pc;
    van.push_back(1);
    do
    {
        mi=-1;
        for(iv=van.begin();iv!=van.end();iv++)
        {
            for(it=t[*iv].begin(),ic=c[*iv].begin(); it!=t[*iv].end(); it++,ic++)
                if(s[*it]==-1)
            {
                if(s[*iv]+*ic<mi||mi==-1)
                {
                    mi=s[*iv]+*ic;
                    pv=iv;//
                    pt=it;
                    pc=ic;
                }
            }
        }
        if(mi!=-1)
        {
            int aui=int(*pt);
            s[*pt]=mi;
            t[*pv].erase(pt);
            c[*pv].erase(pc);
            if(t[*pv].begin()==t[*pv].end())
            {
                it=van.begin();
                while(*it!=*pv)
                    it++;
                van.erase(it);
            }
            van.push_back(aui);
            vandb++;
        }
    }while(vandb!=n&&mi!=-1);
    for(i=2;i<=n;i++)
        if(s[i]==-1)
        g<<0<<" ";
    else g<<s[i]<<" ";
    f.close();
    g.close();
    return 0;
}