#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
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],viz[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];
    }
};

bool comp(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;
    vector<int> q;
    dist[sursa] = 0;
    tata[sursa] = -1;
    viz[sursa] = 1;
    q.push_back(sursa);
    for(int i = 1; i <= n; i++)
    {
        if(i != sursa)
        {
            dist[i] = INF;
            tata[i] = -1;
        }
    }
    int nod;
    int sz;
    int cost;
    int nod2;
    while(!q.empty())
    {
//        for(int i = 0; i < q.size(); i++)
//            cout<<q[i]<<' ';
//        cout<<'\n';
        nod = q.front();
        pop_heap(q.begin(), q.end(), comp);
        q.pop_back();
        sz = graf[nod].size();
        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;
                if(!viz[nod2])
                    {
                        viz[nod2] = 1;
                        q.push_back(nod2);
                        push_heap(q.begin(), q.end(),comp);
//                        for(int i = 0; i < q.size(); i++)
//                            cout<<q[i]<<' ';
//                        cout<<'\n';
                    }
                else
                {
                    int aux = q.back();
                    q.pop_back();
                    q.push_back(aux);
                    push_heap(q.begin(), q.end(),comp);
//                    for(int i = 0; i < q.size(); i++)
//                        cout<<q[i]<<' ';
//                    cout<<'\n';
                }
            }
        }
//        cout<<'\n'<<'\n';
    }
}

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;
}