#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,j,a,b,d,s[50001],n,m,pozi,pozj,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;
                }
            }
        }
        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);
    for(i=2;i<=n;i++)
        if(s[i]==-1)
        g<<0<<" ";
    else g<<s[i]<<" ";
    f.close();
    g.close();
    return 0;
}