#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

struct arc
{
    unsigned short w,l; // w- where; l-length
};

vector <vector <arc> > a;
vector <int> d;

bool cp(arc x, arc y) //cp - compara
{
    return x.l<y.l;
}

void read()
{
    arc t;
    int m; unsigned short n,x;
    cin >> n >> m;
    a.resize(n+1);
    for ( ; m ; m--)
    {
        cin >> x >> t.w >> t.l;
        a[x].push_back(t);
    }
    for (int i=0; i< a.size(); i++)
    {
        sort(a[i].begin(),a[i].end(),cp);
    }
    d.resize(n+1);
    fill(d.begin(),d.end(),-1);
    d[1]=0;
}

void solve()
{
    vector <unsigned short> q;
    q.push_back(1);
    arc x;
    for (int i=0; i<q.size(); i++)
    {
        for (int j=0; j<a[q[i]].size(); j++)
        {
            x=a[q[i]][j];
            if (d[x.w]==-1 || d[x.w]>d[q[i]]+x.l)
            {
                q.push_back(x.w);
                d[x.w]=d[q[i]]+x.l;
            }
        }
    }
}

void ct(int &x)
{
    if (x==-1) x=0;
}

main()
{
    read();
    solve();
    for_each(d.begin()+2,d.end(),ct);
    copy(d.begin()+2,d.end(),ostream_iterator <int> (cout, " "));
}