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

using namespace std;

ifstream F("dijkstra.in");
ofstream G("dijkstra.out");

queue <int> q;
int n, m, x, y, z, c[50003], w[50003];
const int inf = 10000000;
vector<pair<int, int> > l[50005];
vector< pair< int, int > >::iterator b;


int main()
{
    F >> n >> m;
    for(int i = 2; i <= n; ++ i)
        w[i] = inf;
    for(int i = 0; i < m; ++ i)
    {
        F >> x >> y >> z;
        l[x].push_back({y, z});
    }
    q.push(1);
    c[1] = 1;
    while(!q.empty())
    {
        x = q.front();
        c[x] = 0;
        q.pop();
        for(b = l[x].begin(); b != l[x].end(); b++ )
            if(w[(*b).first] > w[x] + (*b).second)
            {
               w[(*b).first] = w[x] + (*b).second;
               if(!c[(*b).first])
                    c[(*b).first] = 1, q.push((*b).first);
            }
    }
    for(int i = 2; i <= n; ++ i)
        w[i] == inf ? G << "0" : G << w[i], G << " ";
    return 0;
}