#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,mi;
    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
    {
        iv=van.begin();
        it=t[*iv].begin();
        ic=c[*iv].begin();
        mi=s[*iv]+*ic;
        pt=it;
        pc=ic;
        pv=iv;
        it++;
        ic++;

        for(;iv!=van.end();iv++)
        {
            for(it=t[*iv].begin(),ic=c[*iv].begin(); it!=t[*iv].end(); it++,ic++)
            {
               if(s[*iv]+*ic<mi)
                {
                    mi=s[*iv]+*ic;
                    pv=iv;//
                    pt=it;
                    pc=ic;
                }
            }
        }
        vector<unsigned int>:: iterator aux;
        aux=pt;
        int aui=int(*aux);
        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);
    }while(s[n]==-1);
    for(i=2;i<=n;i++)
        if(s[i]==-1)
        g<<0<<" ";
    else g<<s[i]<<" ";
    f.close();
    g.close();
    return 0;
}