#include <fstream>
#include <list>
using namespace std;
int a[50001],b[50001];
std::list<pair<int,int> > l[50000];
int main()
{int n,m,i,y,z,x,ok;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        l[x].push_back(make_pair(y,z));
        if(x!=1)
        {
            l[y].push_back(make_pair(x,z));
        }
    }
    list<pair<int,int> > q;
    q.push_back(make_pair(1,0));
    ok=n;
    pair<int,int> w,p,r;
    std::list<pair<int,int> >::iterator k,v;
    while(q.empty()==0)
    {
        k=q.begin();
        w=*k;
        for(k=l[w.first].begin();k!=l[w.first].end();++k)
        {
            p=*k;
            if(a[p.first]==0)
            {
                if(b[p.first]==0 || b[p.first]>w.second+p.second)
                {
                    b[p.first]=w.second+p.second;
                }
                v=q.begin();
                ++v;
                r=*v;
                while(r.second<b[p.first])
                {
                    ++v;
                    r=*v;
                }
                q.insert(v,make_pair(p.first,b[p.first]));
            }
        }
        if(a[w.first]==0)
        {
            a[w.first]=1;
            ok--;
        }
        if(ok==0)
        {
            break;
        }
        q.pop_front();
    }
    for(i=2;i<=n;i++)
    {
        g<<b[i]<<" ";
    }
    f.close();
    g.close();
    return 0;
}