#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];

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(auto i : l[x])
            if(w[i.first] > w[x] + i.second)
            {
               w[i.first] = w[x] + i.second;
               if(!c[i.first])
                    c[i.first] = 1, q.push(i.first);
            }
    }
    for(int i = 2; i <= n; ++ i)
        G << w[i] << " ";
    return 0;
}