//Vasilut
//Dijkstra cu Heapuri

#include<fstream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<utility>


#define pb push_back
#define INF 0x3f3f3f3f
#define mp make_pair
#define NN 50001
#define f first
#define s second


using namespace std;
ofstream out("dijkstra.out");

int n,m;
bool uz[NN];
vector<pair<int,int > > G[NN];
vector<int>dist;


struct comp{
    bool operator() (int i,int j)
    {
        return dist[i] < dist[j];
    }
};

set<int,comp>Q;

void read();
void Dijkstra();
void write();

int main()
{
    read();
    Dijkstra();
    write();
    return 0;
}

void read()
{
    ifstream in("dijkstra.in");
    in>>n>>m;
    for(int x,y,c; m ;--m)
    {
        in>>x>>y>>c;
        G[x].pb(mp(y,c));
    }
}

void write()
{
        for(int i=2;i<=n;i++)
            if(dist[i] == INF )
                out<<0<<" ";
                else
                out<<dist[i]<<" ";
}


void Dijkstra()
{
    dist.assign(n+1,INF);
    dist[1]=0;
    Q.insert(1);
    uz[1]=1;
    int k;
    while(!Q.empty())
        {
            k=*Q.begin();
            Q.erase(Q.begin());
            uz[k]=0;
                for( int i=0; (int ) i<G[k].size(); ++i)
                    if(dist[G[k][i].f] > dist[k] + G[k][i].s )
                    {
                        if(uz[G[k][i].f])
                            Q.erase(G[k][i].f);
                            else
                            uz[G[k][i].f]=1;
                        dist[G[k][i].f]=dist[k] + G[k][i].s;
                        Q.insert(G[k][i].f);
                    }
        }
}