#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int INF = 2100000000;
const int NMAX = 50005;
const char inputFile[] = "dijkstra.in";
const char outputFile[] = "dijkstra.out";

int dist[NMAX],tata[NMAX];
vector< pair<int,int> >graf[NMAX];
vector<int> punctControl;
int n, m;
class Cmp
{
public:
    bool operator()(int a, int b)
    {
        return dist[a] > dist[b];
    }
};

void citeste()
{
    FILE *f = fopen(inputFile, "r");
    fscanf(f, "%d %d", &n,&m);
    int a, b, c;
    for(int i = 0; i < m; i++)
        {
            fscanf(f,"%d %d %d", &a,&b,&c);
            graf[a].push_back(make_pair(b,c));
        }
    /*int x;
    while(f >> x)
        punctControl.push_back(x);*/
}

void dijkstra(int sursa)
{
    //priority_queue<int, vector<int>, Cmp> q;
    queue<int> q;
    dist[sursa] = 0;
    tata[sursa] = -1;
    q.push(sursa);
    for(int i = 1; i <= n; i++)
    {
        if(i != sursa)
        {
            dist[i] = INF;
            tata[i] = -1;
            q.push(i);
        }
    }
    int nod;
    int sz;
    int cost;
    int nod2;
    while(!q.empty())
    {
        nod = q.front();
        sz = graf[nod].size();
        q.pop();
        for(int i = 0; i < sz; i++)
        {
            nod2 = graf[nod][i].first;
            cost = dist[nod] + graf[nod][i].second;
            if(cost < dist[nod2])
            {
                tata[nod2] = nod;
                dist[nod2] = cost;
            }
        }
    }
}

int main()
{
    citeste();
    dijkstra(1);
    FILE *g = fopen(outputFile, "w");
    for(int i = 2; i <=n; i++)
        if(dist[i] == INF)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ", dist[i]);
    return 0;
}