#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define MAX 50021
#define pp pair < int , int >
#define INF (1<<20)

using namespace std;

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

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

priority_queue < pp , vector < pp > , greater < pp > > pq;

bitset < MAX > viz;

int n, m, dist[MAX];

void read()
    {
        int x, y, cst;
        f>>n>>m;
        for(int i=1; i<=m; i++)
        {
            f>>x>>y>>cst;
            v[x].push_back({y, cst});
        }
    }

void dijks()
    {
        for(int i=2; i<=n; i++)
            dist[i]=INF;
        for(int i=2; i<=n; i++)
        {
            pq.push({0, 1});
            while(!pq.empty())
            {
                int nod = pq.top().second;
                int cst = pq.top().first;
                pq.pop();
                if(!viz[nod])
                {
                    viz[nod]=1;
                    for(auto it : v[nod])
                    {
                        if(!viz[it.first])
                        {
                            dist[it.first]=min(dist[it.first], dist[nod]+it.second);
                            pq.push({dist[it.first], it.first});
                        }
                    }
                }
            }
        }
        for(int i=2; i<=n; i++)
            if(dist[i]==INF)
                g<<0<<" ";
            else g<<dist[i]<<" ";
    }

int main()
    {
        read();
        dijks();
    }