#include <cstdio>
#include <set>
#include <iostream>
#include <climits>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX= 50005;
const int INF = 0x3f3f3f3f;
const int inf= INT_MAX;
int dist[NMAX];
set<pair<int,int> > h;
vector <pair<int, int> > v[NMAX];
vector <pair<int, int> >:: iterator it;
void goleste()
{
    while(!h.empty())
    {
        h.erase(h.begin());
    }

}
int main()
{
    FILE *f=fopen("dijkstra.in","r");
    FILE *g=fopen("dijkstra.out","w");
    int n,m;
    fscanf(f,"%d%d",&n,&m);

    for(int i=1; i<=m; i++)
    {
        int from,to,price;
        fscanf(f,"%d%d%d",&from,&to,&price);
        v[from].push_back(make_pair(to,price));

    }

    memset(dist, INF, sizeof dist);


    h.insert(make_pair(0,1));
    while(!h.empty())
    {
        int node = h.begin()->second;
        int d = h.begin()->first;
        //goleste();
        h.erase(h.begin());

        for(it=v[node].begin(); it!=v[node].end(); ++it)
        {
            int to=it->first;
            int cost=it->second;

            if(dist[to]>d+cost)
            {
                dist[to]=d+cost;

                h.insert(make_pair(dist[to],to));

            }





        }





    }
    for(int i=2; i<=n; i++)
    {
        fprintf(g,"%d ",dist[i]);
    }

    return 0;
}