#include <fstream>
#include <vector>
#include <set>
#define DIM 100002
#define INF 1e9

using namespace std;

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

int n, x, y, d, m;
int dist[DIM];

bool inQueue[DIM];

vector<pair<int, int> > graf[DIM];

class compare{
public:
    bool operator() (int a, int b){
        return dist[a] < dist[b];
    }
};

set<int, compare> s;

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; ++ i){
        in>>x>>y>>d;
        graf[x].push_back({y, d});

    }
    dist[1] = 0;
    for(int i = 2; i <= n; ++ i)
        dist[i] = INF;

    inQueue[1] = true;
    s.insert(1);

    while(!s.empty()){
        int currNode = *s.begin();
        inQueue[currNode] = false;
        s.erase(s.begin());
        for(auto it : graf[currNode]){
            int nextNode = it.first;
            int distance = it.second;
            if(dist[currNode] + distance < dist[nextNode]){
                if(inQueue[nextNode] == true){
                    s.erase(s.find(nextNode));
                }
                dist[nextNode] = dist[currNode] + distance;
                s.insert(nextNode);
                inQueue[nextNode] = true;
            }
        }
    }

    for(int i = 2; i <= n; ++ i){
        if(dist[i] == INF)
            out<<"0 ";
        else
            out<<dist[i]<<" ";

    }



    return 0;
}