#include <iostream>
#include <set>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream be("dijkstra.in");
ofstream ki("dijkstra.out");
const int NMAX = 50000, INF = 2000000000;
int n,m;
int best[NMAX + 1];
set <pair <int,int> > h;

class Ut
{
public:
    int to, ar;
};
vector <Ut> v[NMAX + 1];

void beolvas()
{
    int a,b,c;
    be>>n>>m;
    for(int i = 0; i < m; i++)
    {
        be>>a>>b>>c;
        v[a].push_back({b,c});

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


int main()
{
    beolvas();
    h.insert(make_pair(0,1));
    while(!h.empty())
    {
        int now = h.begin()->second;
        h.erase(h.begin());///!!!!
        int meret = v[now].size();
        for(int i = 0; i < meret; i++)
        {
            if(best[v[now][i].to] > best[now] + v[now][i].ar)
            {
                if(best[v[now][i].to] != INF)
                {
                    h.erase(h.find(make_pair(best[v[now][i].to], v[now][i].to)));
                }
                best[v[now][i].to] = best[now] + v[now][i].ar;
                h.insert(make_pair(best[v[now][i].to], v[now][i].to));
            }
        }
    }

    for(int i = 2; i <= n; i++)
    {
        if(best[i] == INF)
            ki<<0<<" ";
        else
            ki<<best[i]<<" ";
    }

    return 0;
}