#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

using PII = pair<int,int>;
using VI = vector<int>;

const int Inf=0x3f3f3f3f;
int N,M;
vector<vector<PII>> G;
VI d;

void Read();
void Dijkstra(int x, VI& d);

int main()
{
    Read();
    Dijkstra(1,d);

    for(int i=2;i<=N;++i)
        if(d[i]!=Inf)
        fout<<d[i]<<" ";
    else fout<<0<<" ";

    fout.close();
}

void Read()
{
    fin>>N>>M;
    G=vector<vector<PII>>(N+1);
    while(M--)
    {
        int x,y,c;
        fin>>x>>y>>c;
        G[x].push_back({y,c});
    }

    fin.close();
}
void Dijkstra(int x, VI& d)
{
    priority_queue<PII, vector<PII>, greater<PII>> Q;

    d[x]=0;
    Q.push({0,x});

    while(!Q.empty())
    {
        int x_nou=Q.top().second, dx=Q.top().first;
        Q.pop();

        if(d[x_nou]<dx) continue;

        for(auto p : G[x_nou])
        {
            int y=p.first, w=p.second;
            if(d[y]>d[x_nou]+w)
                d[y]=d[x_nou]+w;
            Q.push({d[y],y});
        }
    }
}