#include<fstream>
#include<cstring>
#include<queue>
#include<vector>

#define N 50100
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int i,n,m,x,y,z,c,d[N];

priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >h;

vector<pair<int,int> >v[N];

inline void dijkstra(){
    memset(d, INF, sizeof(d));

    d[1] = 0;
    h.push(make_pair(0, 1));

    while(!h.empty())
    {
        x = h.top().second;
        c = h.top().first;
        h.pop();

        if(d[x] != c)
            continue;

        for(vector<pair<int,int> >::iterator it = v[x].begin(); it != v[x].end(); ++it)
            if(d[it->first] > d[x] + it->second)
            {
                d[it->first] = d[x] + it->second;

                h.push(make_pair(d[it->first], it->first));
            }
    }

    for(i = 2; i <= n; ++i)
        if(d[i] == INF)
            g << 0 << ' ';
        else
            g << d[i] << ' ';
}

int main()
{
    f >> n >> m;

    for(i = 1; i <= m; ++i)
    {
        f >> x >> y >> z;

        v[x].push_back(make_pair(y, z));
    }

    dijkstra();

    return 0;
}